時間限制:3000ms單點時限:1000ms內(nèi)存限制:256MB描述公元2411年，人類開始在地球以外的行星建立居住點。在第1326號殖民星上，N個居住點分布在一條直線上。為了方便描述，我們設(shè)第i個居住點的位置是Xi，其中居住著Yi位居民。隨著冬季的到來，一些人口較多的居住點的生態(tài)循環(huán)系統(tǒng)已經(jīng)開始超負荷運轉(zhuǎn)。為了順利度過嚴冬，殖民星上的居民一致同意通過轉(zhuǎn)移到人口較少的居住點來減輕人口眾多的居住點的負荷。遺憾的是，1326殖民星的環(huán)境非常惡劣。在冬季到來前，每個居民點的居民最遠能遷移到距離不超過R的居民點。1326殖民星的居民希望知道，如何安排遷移才能使完成遷移后人口最多的居民點人口最少？注意有可能存在多個居民點位置相同。輸入第一行包含一個整數(shù)T(1 <= T <= 10)，代表測試數(shù)據(jù)的組數(shù)。每組數(shù)據(jù)的第一行包含2個整數(shù)N(1 <= N <= 100000)和R(0 <= R <= 10^9)。以下N行每行包含兩個整數(shù)，Xi和Yi(0 <= Xi, Yi, <= 10^9)。輸出對于每組數(shù)據(jù)輸出遷移后人口最多的居民點人口最少可能的數(shù)目。樣例輸入35 110 8020 2030 10040 3050 105 1010 8020 2030 10040 3050 105 2010 8050 1020 2030 10040 30樣例輸出1005048求算法思路。
1 回答
小唯快跑啊
TA貢獻1863條經(jīng)驗 獲得超2個贊
//這是我提交的代碼，僅供參考 #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;} |
添加回答
舉報
0/150
提交
取消