要求对于每组数据输出迁移后人口最多的居民点人口最少可能的数目？

Question

时间限制:3000ms单点时限:1000ms内存限制:256MB描述公元2411年，人类开始在地球以外的行星建立居住点。在第1326号殖民星上，N个居住点分布在一条直线上。为了方便描述，我们设第i个居住点的位置是Xi，其中居住着Yi位居民。随着冬季的到来，一些人口较多的居住点的生态循环系统已经开始超负荷运转。为了顺利度过严冬，殖民星上的居民一致同意通过转移到人口较少的居住点来减轻人口众多的居住点的负荷。遗憾的是，1326殖民星的环境非常恶劣。在冬季到来前，每个居民点的居民最远能迁移到距离不超过R的居民点。1326殖民星的居民希望知道，如何安排迁移才能使完成迁移后人口最多的居民点人口最少？注意有可能存在多个居民点位置相同。输入第一行包含一个整数T(1 <= T <= 10)，代表测试数据的组数。每组数据的第一行包含2个整数N(1 <= N <= 100000)和R(0 <= R <= 10^9)。以下N行每行包含两个整数，Xi和Yi(0 <= Xi, Yi, <= 10^9)。输出对于每组数据输出迁移后人口最多的居民点人口最少可能的数目。样例输入35 110 8020 2030 10040 3050 105 1010 8020 2030 10040 3050 105 2010 8050 1020 2030 10040 30样例输出1005048求算法思路。

Answer 1

//这是我提交的代码，仅供参考 #include <stdio.h>#include <stdlib.h>#include <math.h> struct Node{    int X;    int Y;    int Y_tmp;    int l;    int r;    int capacity;}node[100001];  int N,R; int cmp(struct Node *a, struct Node *b){    return a->r-b->r;} int Is_Sucess(int middle){    int i,j,start=0;    for(i=0; i<N; i++)    {        node[i].capacity=middle;        j=start;        while(node[i].capacity>0 && node[j].l<=node[i].X && j<N)        {/*          if(node[j].Y_tmp==0)            {                j++;                continue;            }*/            if(node[j].r<node[i].X && node[j].Y_tmp>0)                return 0;            if(node[j].l<=node[i].X && node[j].r>=node[i].X)            {                if(node[i].capacity>=node[j].Y_tmp)                {                    node[i].capacity-=node[j].Y_tmp;                    node[j].Y_tmp=0;                    start=j+1;                }                else                {                    node[j].Y_tmp-=node[i].capacity;                    node[i].capacity=0;                }            }            j++;        }    }    if(node[N-1].Y_tmp>0)        return 0;    return 1;} int Binary_Search(int high, int low){    int i,middle;    while(high!=low)    {        middle=(high+low)/2;        for(i=0; i<N; i++)            node[i].Y_tmp=node[i].Y;        if(Is_Sucess(middle))            high=middle;        else            low=middle+1;    }    return high;} int main(){    int T;    int i,j;    int high;    long long int low;    scanf("%d", &T);    while(T--)    {        scanf("%d%d", &N, &R);        low=0;        high=0;        for(i=0; i<N; i++)        {            scanf("%d%d", &node[i].X, &node[i].Y);            node[i].l=node[i].X-R;            node[i].r=node[i].X+R;            if(high<node[i].Y)                high=node[i].Y;            low+=node[i].Y;        }        qsort(node,N,sizeof(node[0]),cmp);        low=low/N;        high=Binary_Search(high,low);        printf("%d\n",high);    }    system("pause");    return 0;}