題目：
繼百度搜索框大廈之後，百度又於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列)，從而節省了內存開銷，值得借鑒。
摘自 賣火柴的小女孩
