分析得，選取的電視塔的位置應當位于各城市的加權(quán)中位數(shù)位置的右邊最近的城市位置。

理由：對于上述位置A，假設它右邊城市+它本身的人數(shù)為rp,它左邊城市的人數(shù)為lp，由定義rp>=lp。

所以，如果向左移動D距離，則右邊城市不滿意度增加D*rp，左邊減少D*lp<=D*rp，不合算。

同理，向右移動D距離時，同樣有D*rp<=D*lp，不合算。

所以，上述位置為最佳位置。

輸出時應注意輸出格式：有五位小數(shù)。

#include "stdio.h" #include "string.h" #include "stdlib.h" struct city{int p,x; }c[15010]; int cmp(const void *a,const void *b){return (*(city *)a).x-(*(city *)b).x; } int main(){int i,N,sum=0,tmp=0,dist=0;scanf("%d",&N);for(i=0;i<N;i++){scanf("%d%d",&c[i].x,&c[i].p);sum+=c[i].p;}qsort(c,N,sizeof(c[0]),cmp);for(i=0;i<N;i++){tmp+=c[i].p;if(tmp>=sum/2+sum%2){printf("%d.00000",c[i].x);break;}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lostwinder/p/3880563.html

總結(jié)

以上是生活随笔為你收集整理的SGU 114的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。