描述

繼百度搜索框大廈之后，百度又于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 ≤ u_i,d_i ≤ 1000）

輸出

輸出一個正整數，表示選用m個電梯中的一個后，在電梯里按電梯中的按鈕n次后（每次兩個按鈕選一個按），可以到達的最低樓層數。

樣例輸入

10 3 15 4 15 12 7 12

樣例輸出

13

這是一個很簡單的線性規劃的題目（直接模擬做會超時的），設按下上升按鈕的次數和下降按鈕的次數分別問x、y，則約束條件是x+y==n，求ui*x-di*y的最小值，當然保證結果要大于0，把變量x用變量y來表示，帶入方程，這樣就只含有一個變量了，求其極小值，這個想必大家都會做的。
代碼：
#include<iostream> #include<cstdio> using namespace std; #define MAX 0x7fffffff int main(void) {int n,m,j,a,b,ans,max,k;while(scanf("%d %d",&n,&m)!=EOF){max = MAX;for(j = 0 ,ans = 0 ; j < m ; ++j){scanf("%d %d",&a,&b);k = n*a/(a+b);if(n*a%(a+b) == 0)--k;ans = a*(n-k)-b*k;if(ans < max)max = ans;}printf("%d\n",max);}return 0; }

總結

以上是生活随笔為你收集整理的【2012百度之星/资格赛】J:百度的新大厦的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。