学步园

    把所有城市居民看成是seg(l,r,n)，（其中l为该城市居民能迁徙到的最左点，r为能迁徙到的最右点），统一调度。

  贪心调度策略：

• 从左到右依次枚举城市（1到n）：挑选seg来填充它们。填充尽量多。（有一个上限阈值为maxN）
• 挑选seg的时候，事先对seg按照<l,r>排序，挑选seg.r尽量小的，并且seg.l小于当前城市坐标的。因为r越大，越可以留到后面。r为某个城市居民最右可以迁徙到的点。
• 另外挑选seg的时候，如果seg.r比当前城市坐标还要小，说明当前情况下，该seg居民本来只能安顿到之前的城市里，但之前的城市都满员了，所以调度失败。

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
typedef long long int ll;
struct seg{
    int l,r,n;
    seg(int x,int y,int z):l(x),r(y),n(z){}
};
bool test(const vector<int> &p,const vector<seg> &q,int maxN){//q is sorted
    list<seg> segs;
    int N=p.size(),M=q.size();
    if(q.size()==0) return true; 
    int li=0,ln=q[0].n;
    for(int i=0;i<N;i++){
        int x=p[i];
        int n=maxN;
        if(q[li].r<x) return false;
        for(int j=li;j<=M;j++){
          if(j==M) return true;
          if(q[j].l>x) {
            li=j,ln=q[j].n;
            break;
          }
          int tmp=j==li?ln:q[j].n;
          n-=tmp;
          if(n<0) {
            li=j,ln=0-n;
            break;
          }
          // if n>=0 j++....
        }
    }
    return false;
}
typedef pair<int,int> Pair;
int getMin(vector<Pair>&points,int R){
    int N=points.size();
    if(N==0) return 0;
    
    vector<int>p;vector<seg>q;int tt=0;ll ss=0;//@patch: ss can overflow
    for(int i=0;i<N;i++){
        Pair &t=points[i];
        p.push_back(t.first);
        if(t.second)//@patch: ignore seg with seg.n=0
          q.push_back(seg(t.first-R,t.first+R,t.second));
        tt=max(tt,t.second);//@patch
        ss+=t.second;
    }
    int r=tt,l=(ss+N-1)/N; //@patch:ss is long long
    while(l!=r){
        int mid=(l+r)/2;// l+r can overflow? no. l<=10^9,r<=10^9. 2*10^9<2^31
        if(test(p,q,mid)) {r=mid;}
        else l=mid+1;
    }
    return l;
}
int main(){
    int N;cin>>N;
    for(int i=0;i<N;i++){
        int n,r;cin>>n>>r;
        vector<Pair> ps(n,Pair(-1,-1));
        for(int j=0;j<n;j++){ int x,y;cin>>x>>y;ps[j]=Pair(x,y); }
        sort(ps.begin(),ps.end());    
        cout<<getMin(ps,r)<<endl;
    }
    return 0;
}

顺带贴一下用链表存储seg【】的方法：

链表实现seg【】，优点是每次只需要处理头结点对应seg。每次用完一个seg就可以删掉该头节点。

缺点是因为用到二分法，需要多次尝试（test(),具体为贪心法），每次尝试需要新建一个链表seg【】。

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

struct seg{
    int l,r,n;
    seg(int x,int y,int z):l(x),r(y),n(z){}
};
bool test(vector<int> &p,vector<seg> &q,int maxN){//q is sorted
    list<seg> segs;
    int N=p.size();
    for(int i=0;i<q.size();i++) segs.insert(segs.end(),q[i]);/////////////

    for(int i=0;i<N;i++){
        int x=p[i];
        int n=maxN;
        for(list<seg>::iterator it=segs.begin();it!=segs.end();){
            seg &s=*it;//@error: seg s is a copy, so should be seg &s
            if(s.r<x) return false;//some people can go no where
            if(s.l<=x){//[s.l,s.r] has x. and people can go here
               n-=s.n;
               if(n<0) s.n=0-n;
               else s.n=0;
               if(s.n==0) it=segs.erase(it);
               if(n<=0) break;
            }
            else break;
        }
    }
    return segs.size()==0;
}
typedef pair<int,int> Pair;
int getMin(vector<Pair>&points,int R){
    int N=points.size();
    if(N==0) return 0;
    
    vector<int>p;vector<seg>q;int ss=0;long long int tt=0;/////////////////////
    for(int i=0;i<N;i++){
        Pair &t=points[i];
        p.push_back(t.first);
        if(t.second)///////////////////////
        q.push_back(seg(t.first-R,t.first+R,t.second));
        ss=max(ss,t.second);//////////////////////
        tt+=t.second;
    }
    int r=ss,l=tt/N+(tt%N?1:0);///////////////////////
    while(l!=r){
        int mid=(l+r)/2;
        if(test(p,q,mid)) {r=mid;}
        else l=mid+1;
    }
    return l;
}
int main(){
    int N;cin>>N;
    for(int i=0;i<N;i++){
        int n,r;cin>>n>>r;
        vector<Pair> ps(n,Pair(-1,-1));
        for(int j=0;j<n;j++){ int x,y;cin>>x>>y;ps[j]=Pair(x,y); }
        sort(ps.begin(),ps.end());    
        cout<<getMin(ps,r)<<endl;
    }
    return 0;
}