XCPC第十三站，贪心问题

一.区间选点

        我们采取这样的策略来选点：step（1）将区间按照右端点的大小从小到大排序；step（2）从前往后依次枚举每个区间，如果当前区间中已经包含点，直接pass，否则选当前区间的右端点。因为右端点是最容易被下一个区间包含进去的，所以我们每次选择的都是当前情况下的局部最优解，这种策略就叫作贪心。
        设最优解的点数是ans，按照算法找到的点数是cnt，下面我们证明ans == cnt。首先证明ans<=cnt。根据算法思路，这样选择以后每个区间都包含了点（否则会选右端点），因此算法得到一个可行解。又ans是所有可行解的最小值，因此ans<=cnt。再证明ans>=cnt。如果要执行选一个新的点的操作，那么后一个区间和前一个区间一定无交集。这样一来，我们就至少得到了cnt个互不相交的区间，每个这样的区间我们都选了它的右端点。要覆盖这些区间至少需要cnt个点，因此ans>=cnt。终上，ans == cnt。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int res;
struct range
{int l,r;bool operator< (const range W)const{return r<W.r;}
}range[N];
int main()
{int n;cin>>n;//要从0开始读入而不能从1开始读入，因为排序的是编号从0到（n-1）的数据，如果读到n的话会导致最后一个数据没有排序。//从小到大枚举每个区间for(int i = 0;i<n;i++){int a,b;cin>>a>>b;range[i] = {a,b};}sort(range,range+n);//ed表示枚举的上一个区间的右端点。初始时赋值为负无穷，这是因为第一次总是要加点的。int ed = -2e9;//要从0开始不能从1开始，理由同上for(int i = 0;i<n;i++){//上一个区间的右端点小于当前区间的左端点，说明两个区间没有交集，那么就要选一个新的点if(ed<range[i].l){res++;//更新右端点的值ed = range[i].r;}}cout<<res<<endl;
}

二.最大不相交区间数量

        本题代码与上一题完全相同。下面我们来说明为什么按照上题策略选出的点数即为最大不相交区间数量。设ans为最大不相交区间数量，cnt为按照算法找出的区间数量。根据上题，根据算法选出的区间没有交集，因此是一个可行解。而ans是可行解的最大值，因此ans>=cnt。再证明ans<=cnt。采用反证法。假设ans>cnt，说明我们可以找到ans个互不相交的区间，要用点把这些区间覆盖至少需要ans>cnt个点。但是根据第一题，cnt个点已经可以把所有选出的区间覆盖，矛盾。终上，ans ==cnt。

三.区间分组

        对于本题，我们的策略如下：step（1）将所有区间按照左端点从小到大排序；step（2）从前往后枚举所有区间，枚举当前已有的所有组，判断能否将该区间放进已有的某个组中（即判断某个是否有某个组的区间的右端点最大值小于当前区间的左端点，若<，可以放机；否则无法放进）。若可以放进某个组，就放进去并更新该组右端点的最大值；若不存在这样的组，就开一个新组把这个区间放进去。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100010;
struct range
{int l,r;//重载小于号bool operator<(const range W) const{return l<W.l;}
}range[N];
int main()
{int n;cin>>n;for(int i = 0;i<n;i++){int a,b;cin>>a>>b;range[i] = {a,b};}//将区间按照左端点从小到大排序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);//否则这样的区间存在，放进这个组即可。为了平衡组数，要把堆顶弹出（否则算heap元素个数的时候会多算一个），并且让当前区间的右端点入堆，参与最小最右端点的“选拔”else if(heap.top()<range[i].l){//此时可以放进某个组，为了更新最右端点的最小值我们要把rangeheap.pop();heap.push(range[i].r);}}cout<<heap.size()<<endl;return 0;
}

        下面我们证明根据这种策略得到的组数就是答案。记正确答案为ans，根据算法选出的答案是cnt，那么由于算法可以选出一种可行方案，ans<=cnt。而怎么证明ans>=cnt呢？我们考察最后一次开新组的时刻。

        在该时刻，前cnt-1组的max_r都要比当前区间的l大（也就是要开新组的情形）。但是由于我们是按照左端点从小到大排序的，而该区间在最后才被放进去，因此它的l要大于前面所有max_r的区间的l，故它的l就是前面这些max_r属于的区间的一个交点。加上该区间本身，一共有cnt个区间，它们存在交集，因此必须把它们分开，因此ans>=cnt。终上，ans == cnt。

四.区间覆盖

        我们采取这样的策略：step（1）将所有区间按照左端点从小到大排序；step（2）从前往后枚举每个区间，每次选择有可能覆盖左端点（start）的区间中右端点最靠右的区间（贪心的），再讲start更新成右端点的最大值。为什么按照这种策略得到的区间数目就是要求的答案呢？假设最佳方案选出的区间数是ans，算法选出的区间数是cnt。我们选择答案的区间组和算法的区间组的第一个不同的区间（假设是第二个），那么由于算法选择的是可能覆盖左端点的右端点最靠右的区间，因此有r1<=r2.又要不留缝隙，所以l1<=r1。所以l1<=r1<=r2。因此我们可以把上面的区间换成下面的区间。对其它不同的区间做类似操作，便可知道cnt == ans。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int s,t,n,res;
struct range
{int l,r;//重载小于号bool operator < (const range W)const{return l<W.l;}
}range[N];
int main()
{cin>>s>>t>>n;for(int i = 0;i<n;i++){int a,b;cin>>a>>b;range[i].l = a;range[i].r = b;}//将区间按照左端点从小到大排序sort(range,range+n);bool flag = false;//双指针算法，依次处理每个区间for (int i = 0; i < n; i ++ ){//选择可能覆盖左端点的区间中右端点最靠右的区间int j = i, r = -2e9;while (j < n && range[j].l <= s){r = max(r, range[j].r);j ++ ;}
//如果所有可能覆盖左端点的区间中右端点最靠右的区间的右端点都够不到给定区间的左端点，说明无法覆盖if (r < s){res = -1;break;}
//否则能成功覆盖，所需的区间数加一res ++ ;//如果r>=t说明给定的区间已经被完全覆盖，不再需要执行循环，退出即可if (r >= t){flag = true;break;}
//更新s和i的值，进行下一轮s = r;i = j - 1; }if (!flag) res = -1;printf("%d\n", res);return 0;
}

五.排队打水

        假设第i个打水的人用时为ti，那么总的等待时间就应该是t1*（n-1）+t2*（n-2）+……+tn-1这里我们直接给出一种贪心的策略：按照用时的多少从小到大排队。下面我们证明这种方法的等待时间是最少的。下面假设t1<t2<……tn。假若最优解不是按照时间长短来依次打水，那么一定存在相邻的两个人（记为j和tj+1）满足tj>tj+1。现在我们将这两个人打水的顺序调换，不影响其他人的等待时间，但是我们减少了tj*（n-j）+tj+1*（n-j-1）-tj+1*（n-j）-tj*（n-j-1） = （tj - tj+1）>0，时间减少，这与当前解已是最优解矛盾！

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
//结果可能很大
long long res;
int t[N];int main()
{int n;cin>>n;//因为排序从t这个指针开始，所以我们读入时要从下标0开始读入for(int i = 0;i<n;i++) cin>>t[i];sort(t,t+n);//因为下标从0开始了，所以乘的数要相应地变成(n-i-1)for(int i = 0;i<n;i++)  res+=(n-i-1)*t[i];cout<<res;return 0;
}

六.货仓选址

        我们首先将坐标按照从小到大的顺序排好。假设选址的位置为x，商店的位置分别为x1,x2,x3,……，xn。那么距离之和f（x）= |x-x1|+|x-x2|+……+|x-xn|。我们将它们两两合成一组，那么就是f（x） = |x-x1|+|x-xn|+|x-x2|+|x-xn-1|+……。根据绝对值不等式，f（x）>=|xn-x1|+|xn-1 - x2|+……而等号恰好可以同时取得（即x在中位数的地方）。如图——

#include <algorithm>
#include<iostream>
using namespace std;const int N = 100005;int n, res;
int a[N];int main()
{cin>>n;for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);sort(a, a + n);for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n >> 1]);printf("%d\n", res);return 0;
}

七.耍杂技的牛

        下面风格给出一种贪心策略：

#include<iostream>
#include<limits.h>
#include<algorithm>
using namespace std;
const int K = 50010;
int sum;
int res = INT_MIN;
typedef pair<int,int> PII;
PII cows[K];
int main()
{int N;cin>>N;for(int i = 0;i<N;i++){int w,s;cin>>w>>s;cows[i] = {w+s,w};}sort(cows,cows+N);for(int i = 0;i<N;i++){int w = cows[i].second,s = cows[i].first - w;res = max(res,sum - s);sum+=w;}cout<<res;return 0;
}