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

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)。
输出
对于每组数据输出迁移后人口最多的居民点人口最少可能的数目。
样例输入
3
5 1
10 80
20 20
30 100
40 30
50 10
5 10
10 80
20 20
30 100
40 30
50 10
5 20
10 80
50 10
20 20
30 100
40 30

样例输出
100
50
48
求算法思路。

Answer 1

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