1561

Toduring

jieHeEternity

wssdl
xiuzhiyuan
AcWing2AK

ZagY

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e4+10;

int n;
int res = -2e9;
int sum;
struct Cow
{
int w, s;
bool operator<(const Cow& C)const
{
return w+s<C.w+C.s;// 按w+s从小到大把牛排序
}
} cows[N];

int main()
{
scanf("%d",&n);
for (int i = 0; i < n; i++) scanf("%d%d",&cows[i].w,&cows[i].s);
sort(cows, cows+n);
for (int i = 0; i < n; i++)
{
res = max(res, sum - cows[i].s);
sum += cows[i].w; // 当只有一头牛时危险系数为-s
}
printf("%d\n",res);
}



#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;

int n;
int q[N];

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

sort(q, q + n);

int res = 0;
for (int i = 0; i < n; i ++ ) res += abs(q[i] - q[n / 2]);

printf("%d\n", res);
return 0;
}


/*
t1,t2,t3,......,tn 后面n-1个人都得等t1时间,n-2个人都得t2时间......
t1*(n-1) + t2*(n-2) + ... +t(n-1)*(1)
*/
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
int n;
int a[N];
ll ans;

int main()
{
scanf("%d",&n);
for (int i = 0; i <=n; i++)
scanf("%d",&a[i]);

sort(a , a+n);

for (int i = 0; i <n; i++)
ans += a[i] * (n-i-1);

printf("%lld\n",ans);
return 0;
}


#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
// 哈弗曼树,每次合并重量最小的两堆果子
int main()
{
int n;
scanf("%d", &n);

priority_queue<int, vector<int>, greater<int>> heap;
while (n -- )
{
int x;
scanf("%d", &x);
heap.push(x);
}

int res = 0;
while (heap.size() > 1)
{
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
res += a + b;
heap.push(a + b);
}

printf("%d\n", res);
return 0;
}


### 题目描述

1≤N≤105,
−10^9≤ai≤bi≤10^9,
−10^9≤s≤t≤10^9

#### 输入样例

1 5
3
-1 3
2 4
3 5


#### 输出样例

2


1.将所有区间按照左端点从小到大排序
2.从前往后依次枚举各区间,在所能覆盖指定区间的区间中,找到右端点最靠右的那个,然后将st更新为右端点的值

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int n;
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return l < W.l;
}
}range[N];

int main()
{
int st, ed;// 指定线段的两个端点左st右ed
scanf("%d%d", &st, &ed);
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf("%d%d", &range[i].l, &range[i].r);
}

sort(range, range + n);

int res = 0;
bool success = false;
for (int i = 0; i < n; i ++ )
{
int j = i, r = -2e9;
while (j < n && range[j].l <= st)// 在所有左端点在st之前的区间中找
{
r = max(r, range[j].r);// 找右端点最靠右的那一个
j ++ ;                 // 记录这是找到第几个区间了
}

if (r < st)                // 如果这些区间连最右端点都在st左边
{
res = -1;              // 就省省力气break掉,不可能拼成
break;
}
// 如果最右端点在st右边,说明有戏,继续往下拼
res ++ ;                   // 记下这个最右端点所在的区间,把它的右端点设为新的st
if (r >= ed)               // 往下拼之前先等一等,若刚才那个右端点比指定线段的ed还右
{
success = true;        // 那就已经直接拼成了,不用继续往下拼了
break;
}

st = r;                    // 刚才提到右端点设为新st
i = j - 1;                 // 刚才记录第几个区间的时候,找最右找到头,多算了一个,这里减回来
}

if (!success) res = -1;        // 没拼成res记为-1,拼成res记为用了几个区间
printf("%d\n", res);

return 0;
}


#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int n;
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return l < W.l;
}
}range[N];

int main()
{
int st, ed;// 指定线段的两个端点左st右ed
scanf("%d%d", &st, &ed);
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf("%d%d", &range[i].l, &range[i].r);
}

sort(range, range + n);

int res = 0;
bool success = false;
for (int i = 0; i < n; i ++ )
{
int j = i, r = -2e9;
while (j < n && range[j].l <= st)// 在所有左端点在st之前的区间中找
{
r = max(r, range[j].r);      // 找右端点最靠右的那一个
j ++ ;                       // 记录这是找到第几个区间了
}

if (r < st)                      // 如果这些区间连最右端点都在st左边
{
res = -1;                    // 就省省力气break掉,不可能拼成
break;
}
// 如果最右端点在st右边,说明有戏,继续往下拼
res ++ ;                         // 记下这个最右端点所在的区间,把它的右端点设为新的st
if (r >= ed)                     // 往下拼之前先等一等,若刚才那个右端点比指定线段的ed还右
{
success = true;              // 那就已经直接拼成了,不用继续往下拼了
break;
}

st = r;                          // 刚才提到右端点设为新st
i = j - 1;                       // 刚才记录第几个区间的时候,找最右找到头,多算了一个,这里减回来
}

if (!success) res = -1;              // 没拼成res记为-1,拼成res记录用了几个区间
printf("%d\n", res);

return 0;
}


#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>

using namespace std;
const int N = 100010;

int n;
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return l < W.l; // 左区间从小到大排序
}
}range[N];

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf("%d%d", &range[i].l, &range[i].r);
}

sort(range, range + n);

priority_queue<int, vector<int>, greater<int>> heap;// 小顶堆

for (int i = 0; i < n; i ++ )//从前往后枚举每个区间，判断此区间能否将其放到现有的组中
{
// 当前区间的左端点比现有组中最小的右端点还小,放到任何一组都会有相交部分
if (heap.empty() || heap.top() >= range[i].l){
heap.push(range[i].r);// 不可合并,只能新开一组
}
else {                    // 可以合并
heap.pop();
heap.push(range[i].r);// 更新合并后的区间右端点位置
}
}
printf("%d\n", heap.size());
return 0;
}


#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100100;

int n;
int b[2 * N], idx;

int main()
{
scanf ("%d", &n);
for(int i = 0; i < n; i ++)
{
int l, r;
scanf("%d %d", &l, &r);
b[idx ++] = l * 2;
b[idx ++] = r * 2 + 1;
}

sort(b, b + idx);

int res = 1, t = 0;
for(int i = 0; i < idx; i ++)
{
if(b[i] % 2 == 0) t ++;
else t --;
res = max(res, t);
}
printf ("%d\n", res);
return 0;
}


#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;

struct Range
{
int l,r;
bool operator<(const Range&w)const
{
return r<w.r;
}
}range[N];

int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);
sort(range,range+n);
int res=0,ed=-2e9;
for(int i=0;i<n;i++)
{
if(ed<range[i].l)
{
res++;
ed=range[i].r;
}
}
printf("%d",res);
return 0;
}


### 题目描述

1≤N≤105,
−109≤ai≤bi≤109

#### 输入样例

3
-1 1
2 4
3 5


#### 输出样例

2


#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int n;
struct Range // 区间结构体
{
int l, r;
bool operator< (const Range &W)const
{
return r < W.r;   // 重载<按区间右端点排序
}
}range[N];

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

sort(range, range + n);

int res = 0, ed = -2e9; // 用ed存储上一个定好的点的位置
for (int i = 0; i < n; i ++ )
if (ed < range[i].l)
{
res ++ ;        // 只要当前区间无法覆盖上一个点的坐标就要选新的点了
ed = range[i].r;
}
printf("%d\n", res);
return 0;
}


#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int n;
struct Range // 区间结构体
{
int l, r;
bool operator< (const Range &W)const
{
return r < W.r;   // 重载<按区间右端点排序
}
}range[N];

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

sort(range, range + n);

int res = 0, ed = -2e9; // 用ed存储上一个定好的点的位置
for (int i = 0; i < n; i ++ )
if (ed < range[i].l)
{
res ++ ;        // 只要当前区间无法覆盖上一个点的坐标就要选新的点了
ed = range[i].r;
}
printf("%d\n", res);
return 0;
}