区间问题
AcWing905 区间选点
题意：有n个闭区间，在数轴上选一点使所有区间至少覆盖一个点，求出最少点的数量。
思路：以右端点来取，从小到大枚举右端点，每次把点加在未覆盖点的区间的右端点，可得到最少的数量。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct range
{
int l,r;
}edge[N];
int cmp(range x,range y)
{
return x.r<y.r;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>edge[i].l>>edge[i].r;
sort(edge,edge+n,cmp);
int ans=1,cnt=edge[0].r;
for(int i=1;i<n;i++)
{
if(edge[i].l>cnt)
{
ans++;
cnt=edge[i].r;
}
}
cout<<ans<<endl;
return 0;
}
AcWing 906. 区间分组
题意：将区间分成若干组，组内区间两两之间不能有交集，且组数要尽量少。
思路：将左端点从小到大排序，用一个小根堆来存储当前区间前面的所有区间的右端点，每次将当前区间的左端点与堆顶（最小的右端点）进行比较，若没有交集，则将该区间加入组中，否则放入新的组。这里放入组中是将它直接放入组里区间右端点最小的一组，这样就不用去循环遍历找合适的区间了，因为如果右端点最小的一个组里都不能放入，那其他的组一定也放不了。
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=1e5+10;
struct range
{
int l,r;
}edge[N];
int cmp(range x,range y)
{
return x.l<y.l;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>edge[i].l>>edge[i].r;
sort(edge,edge+n,cmp);
priority_queue<int,vector<int>,greater<int>> heap;//小根堆
for(int i=0;i<n;i++)
{
auto r=edge[i];
if(heap.empty()||heap.top()>=r.l)
heap.push(r.r);//新建一个组
else
{
heap.pop();
heap.push(r.r);
}
}
cout<<heap.size()<<endl;
return 0;
}AcWing 907. 区间覆盖
题意：用给定的区间来覆盖区间[st,ed]，求最少的覆盖区间数。
思路：将所有区间按左端点从小到大排序，依次枚举选出能覆盖st且其右端点最大的一个区间，再将st更新为这个右端点的值，以此类推，直至覆盖到ed。
注意点：①标志flag不能省，因为可能不存在可以覆盖到ed的，但是一直满足tmp>st，这种情况也是不可以的。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct range
{
int l,r;
}edge[N];
int cmp(range x,range y)
{
return x.l<y.l;
}
int main()
{
int st,ed,n;
scanf("%d%d",&st,&ed);
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&edge[i].l,&edge[i].r);
sort(edge,edge+n,cmp);
int flag=0,res=0;
for(int i=0;i<n;i++)
{
int j=i,tmp=-2e9;
while(j<n&&edge[j].l<=st)
{
tmp=max(tmp,edge[j].r);
j++;
}
if(tmp<=st)
{
res=-1;
break;
}
res++;
if(tmp>=ed)
{
flag=1;
break;
}
st=tmp;
i=j-1;
}
if(flag)
printf("%d\n",res);
else
printf("-1\n");
return 0;
}AcWing 148. 合并果子
题意：合并任意两堆果子，代价是两堆果子的总和，求合并成一堆后最小的总代价；
思路：每次合并最小的两堆，用优先队列来存储，其实就是哈夫曼树。
#include<iostream>
#include<queue>
using namespace std;
int main()
{
int n;
cin>>n;
priority_queue<int,vector<int>,greater<int>> heap;
int x,res=0;
for(int i=0;i<n;i++)
{
cin>>x;
heap.push(x);
}
while(heap.size()>1)
{
int a=heap.top();
heap.pop();
int b=heap.top();
heap.pop();
res+=a+b;
heap.push(a+b);
}
cout<<res<<endl;
return 0;
}AcWing 913. 排队打水（排序不等式）
题意：怎样才能使所有人等待的时间最短。
思路：打水时间短的先上。证明：假设已经按从小到大的顺序排好了，则总时间为a1+(a1+a2)+(a1+a2+a3)+...+(a1+a2+...+an-1)，a1<a2，如果交换a1,a2，那么总时间肯定变长了。
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int t[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>t[i];
sort(t,t+n);
long long res=0;
for(int i=0;i<n;i++)
res+=t[i]*(n-1-i);
cout<<res<<endl;
return 0;
}AcWing 104. 货仓选址(绝对值不等式）
思路：f(x)=|x-x1|+|x-x2|+...+|x-xn|,即f(x)=(|x-x1|+|x-xn|)+(|x-x2|+|x-x(n-1))+...
要使f(x)最小，可发现每次当x取在另两个数之间时可得到最小的距离xn-x1，对于所有的点以此类推可得当x位于所有点中最中间两点之间时f(x)最小，因为此时x一定在所有的两点之间了。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
long long res=0;
for(int i=0;i<n;i++)
res+=abs(a[n/2]-a[i]);
cout<<res<<endl;
return 0;
}AcWing 125. 耍杂技的牛 （推公式）
题意：每头牛的风险等于它上面所有牛的体重之和减去它自己的强壮值，求最大风险的最小可能值。
思路：按wi+si从小到大排序，所得最大值最小。
证明：交换前①第i头牛承重sum-s[i],第i+1头牛承重sum+w[i]-s[i+1]
交换后② sum+w[i+1]-s[i] sum-s[i+1]
要使1中的最大值大于2中的最大值，则w[i]-s[i+1]>w[i+1]-s[i]，即w[i]+s[i]>w[i+1]+s[i+1]，所以如果存在任意两头牛之间s+w是逆序的，那么危险系数是更大的，所以从小到大排序是最优的。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e4+10;
typedef long long ll;
typedef pair<ll,int> PII;
const int INF=0x3f3f3f3f;
ll w[N],s[N];
PII c[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lld%lld",&w[i],&s[i]);
c[i]={w[i]+s[i],w[i]};
}
sort(c,c+n);
ll res=-INF,sum=0;
for(int i=0;i<n;i++)
{
int s=c[i].first-c[i].second,w=c[i].second;
res=max(res,sum-s);
sum+=w;//头上所有重量
}
printf("%lld\n",res);
return 0;
}