程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 線性規劃——由百度新大廈說開去

線性規劃——由百度新大廈說開去

編輯:關於C

題目:                                                                                                                                                
繼百度搜索框大廈之後,百度又於2012年初在深圳奠基了新的百度國際大廈,作為未來百度國際化的橋頭堡。不同於百度在北京的搜索框大廈,新的百度國際大廈是一棟高樓,有非常多的樓層,讓每個樓中的電梯都能到達所有樓層將是一個極為不明智的設計。因此,設計師給出了一個特別的設計——大廈一共有m個電梯,每個電梯只有兩個按鈕,(針對第i個電梯)兩個按鈕分別可以使電梯向上上升ui層或向下下降di層;百度國際大廈很高,你永遠到不了頂層,也就是說電梯沒有上限,但是,電梯不可以鑽入地下,也就是說是有下限的。我們將每層樓用整數標記,為了體現IT公司的特質,我們以0作為地面這一層的標記。
如果你某天在百度國際大廈的0層,僅可以選擇m個電梯中的一個乘坐(不可以中途換電梯),請你計算,你按電梯中的按鈕n次後(每次兩個按鈕選一個按),可以到達的最低樓層數。
輸入:輸入的第一行包括兩個整數,分別為n和m(1 ≤ n ≤ 1,000,000,1 ≤ m ≤ 2,000),表示按電梯按鈕的次數和大廈中的電梯數量。接下去的m行,每行包括2個由空格分割的數字,分別表示了提供的m個電梯中的某一個的上行按鈕上升一次的層數ui和下行按鈕下降一次的層數di(1 ≤ ui,di ≤ 1000)
輸出:輸出一個正整數,表示選用m個電梯中的一個後,在電梯裡按電梯中的按鈕n次後(每次兩個按鈕選一個按),可以到達的最低樓層數。
樣例輸入
10 3
15 4
15 12
7 12
樣例輸出
13
提示按鈕上的移動樓層數無法改變,比方說從8層向下9層是不可行的。
思路                                                                                                                                                        
這是百度之星資格賽的最後一題,由於本人只是做工程應用的,很少涉及算法上的問題,因此此題使用傳統的方法,也就是最容易思考到的方法測試通過了,但是太耗時,度娘當然是不給過的,我自己也測試了下,當按下的次數特別大時,運算時間要十來秒。所以這裡采用線性規劃的方法可以簡化算法,同時大大提高程序的效率。
傳統方法                                                                                                                                                                                            
共m個電梯,按n次。首先是輸入每個電梯上和下的樓層數。分別用up[m]和down[n]表示。則第i個電梯上升up[i]層,下降down[i]層。
然後一個電梯一個電梯的比較,在第i個電梯中,假設上升按了j次,則下降就按了n-j次,最後電梯所在樓層為up[i]*j-down[i]*(n-j),當然最後所在樓層數必須為正,即大於0,所以需要將該值<=0的捨去。
代碼如下:
 
 1 #include <stdio.h>
 2 #include <time.h>
 3
 4 int main()
 5 {
 6     long n;
 7     int m;
 8     scanf("%ld %d",&n,&m);
 9
10     int up[m];
11     int down[m];
12     for(int i=0;i<m;i++)
13     {
14         scanf("%d %d",&up[i],&down[i]);
15     }
16
17     long temp=0;
18     long value=1000000;
19     float time1=clock();
20     for(int i=0;i<m;i++)
21     {
22         for(long j=0;j<m+1;j++)
23         {
24             temp=j*up[i]-(m-j)*down[i];
25             if( (temp>0)&&(value>temp) )
26                value=temp;
27         }
28     }
29     float time2=clock();
30
31     printf("%ld\n",value);
32     printf("%.2fms",time2-time1);
33     return 0;
34 }
 
正確的結果是可以得出的。clock()函數是拿來測試運算執行時間的,當n取的值非常大時,可以看到是相當耗時的。網上有一些代碼是時間超過了限制,大概使用的是這種方法,因為這種方法最容易想到,把所有可能情況都拿出來進行比較。下面利用線性規劃進行優化,從中可以看到數學的強大威力。
線性規劃的方法                                                                                                                                   
先來做一下小小的分析。還是一個電梯一個電梯的比較,當在第i個電梯中時:
上升:up[i]    下降:down[i]
假設上升按了j次,則下降就按了(n-j)次,最後的樓層為W=up[i]*j-down[i]*(n-j)=(up[i]+down[i])*j-down[i]*n
要是W最小(W>0),通過該式可以看出,要求W>0時的最小值,就是要找出滿足該最小值時的j的值。
當然W>0時的最小值,即j滿足j>down[]*n/(up[i]+down[i]),只要求出了滿足該式的j的最小值,帶入W表達式中即可求出滿足W>0的W的最小值。
有一個問題,倘若存在j使得W=0時,因為最後不能在第0層,所以j的值要取down[]*n/(up[i]+down[i])+1,這是為了防止除出來剛好為整數的情況。
采用此種方法的代碼和上述常規方法不同的地方就在for循環的處理上,其他地方都一樣,見下:
 
for(int i=0;i<m;i++)
    {
        int k=n*down[i]/(up[i]+down[i]) + 1;
        temp=k*up[i]-down[i]*(n-k);
        if(value>temp)
            value=temp;
    }
 
這裡只有一重循環,比之前面的兩重循環要優化了很多,尤其是當n的值很大時效率就體現出來了。
 後記                                                                                                                                          
在網上還看到了其他好的代碼,比如只聲明兩個變量,表示上升和下降的樓層,在循環中計算每個樓層時就是用這兩個變量,這樣就不需要定義兩個一維數組(或二維數組也行,只不過二維數組是2列),從而節省了內存開銷,值得借鑒。

 

 

摘自 賣火柴的小女孩

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved