1242：網(wǎng)線主管

時間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 14497 ??? 通過數(shù): 3040

【題目描述】

仙境的居民們決定舉辦一場程序設(shè)計區(qū)域賽。裁判委員會完全由自愿組成，他們承諾要組織一次史上最公正的比賽。他們決定將選手的電腦用星形拓?fù)浣Y(jié)構(gòu)連接在一起，即將它們?nèi)窟B到一個單一的中心服務(wù)器。為了組織這個完全公正的比賽，裁判委員會主席提出要將所有選手的電腦等距離地圍繞在服務(wù)器周圍放置。

為購買網(wǎng)線，裁判委員會聯(lián)系了當(dāng)?shù)氐囊粋€網(wǎng)絡(luò)解決方案提供商，要求能夠提供一定數(shù)量的等長網(wǎng)線。裁判委員會希望網(wǎng)線越長越好，這樣選手們之間的距離可以盡可能遠(yuǎn)一些。

該公司的網(wǎng)線主管承接了這個任務(wù)。他知道庫存中每條網(wǎng)線的長度（精確到厘米），并且只要告訴他所需的網(wǎng)線長度（精確到厘米），他都能夠完成對網(wǎng)線的切割工作。但是，這次，所需的網(wǎng)線長度并不知道，這讓網(wǎng)線主管不知所措。

你需要編寫一個程序，幫助網(wǎng)線主管確定一個最長的網(wǎng)線長度，并且按此長度對庫存中的網(wǎng)線進(jìn)行切割，能夠得到指定數(shù)量的網(wǎng)線。

【輸入】

第一行包含兩個整數(shù)N和K，以單個空格隔開。N（1 ≤ N ≤ 10000）是庫存中的網(wǎng)線數(shù)，K（1 ≤ K ≤ 10000）是需要的網(wǎng)線數(shù)量。

接下來N行，每行一個數(shù)，為庫存中每條網(wǎng)線的長度（單位：米）。所有網(wǎng)線的長度至少1m，至多100km。輸入中的所有長度都精確到厘米，即保留到小數(shù)點后兩位。

【輸出】

網(wǎng)線主管能夠從庫存的網(wǎng)線中切出指定數(shù)量的網(wǎng)線的最長長度（單位：米）。必須精確到厘米，即保留到小數(shù)點后兩位。

若無法得到長度至少為1cm的指定數(shù)量的網(wǎng)線，則必須輸出“0.00”（不包含引號）。

【輸入樣例】

4 11 8.02 7.43 4.57 5.39

【輸出樣例】

2.00

【分析】

? ? ? ? 需要等長網(wǎng)線數(shù)量已知，要求盡可能長，可以枚舉所有網(wǎng)線可能的長度len∈[0, max] , 計算出每種長度下網(wǎng)線的數(shù)量，時間復(fù)雜度為 O(max*n)。以樣例數(shù)據(jù)為例，已知庫存網(wǎng)線4根，長度分別是8.02, 7.43, 4.57, 5.39。現(xiàn)在需要11根等長的網(wǎng)線，盡可能長。從輸出數(shù)據(jù)看，長度為2.00，也就是說，第一根分割出4根，第二根分割出3根，第三根分割出2根，第四根分割出2根，共11根。

【參考代碼1】枚舉超時代碼

#include <stdio.h> #define N 10000010 double lens[N]; int main() {int n; //庫存的網(wǎng)線數(shù)int k; //需要的網(wǎng)線數(shù)量int i,x,cnt;double mlen=0;scanf("%d%d",&n,&k);for(i=0;i<n;i++){scanf("%lf",&lens[i]);lens[i]*=100;}x=1;while(1){cnt=0; for(i=0;i<n;i++)cnt+=lens[i]/x;if(cnt>=k){if(x>mlen)mlen=x;x++;}elsebreak;}printf("%.2lf\n",mlen/100);return 0; }

? ? ? ? 枚舉法，O(max*n)鐵定超時，如上述代碼。這道題可以用二分法

【參考代碼2】

#include <stdio.h> #define N 10000010 double lens[N]; int main() {int n; //庫存的網(wǎng)線數(shù)int k; //需要的網(wǎng)線數(shù)量int i;int xl=0,xr=N,xm; //根據(jù)xl和xr，找出最大的xm int cnt; //可以切分出來的網(wǎng)線數(shù)量 double mlen=0; //切割的最長長度 scanf("%d%d",&n,&k);for(i=0;i<n;i++){scanf("%lf",&lens[i]);lens[i]*=100;}while(xr>=xl){cnt=0;xm=(xr+xl)/2;for(i=0;i<n;i++)cnt+=lens[i]/xm;if(cnt<k)xr=xm-1;else{xl=xm+1;if(xm>mlen)mlen=xm;}}printf("%.2lf\n",mlen/100);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1242

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1242：网线主管）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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