【2012 百度之星资格赛 J:百度的新大厦】

J:百度的新大厦

时间限制:: 1000ms
内存限制:: 65536kB

描述

继百度搜索框大厦之后，百度又于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次后（每次两个按钮选一个按），可以到达的最低楼层数。

样例输入

样例输出

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int CCalLowest(int u, int d, int n)
 5 {
 6     int downTime = u * n / (u + d);
 7     int upTime   = n - downTime;
 8     
 9     int min = u * upTime - d * downTime;
10     
11     for (int i = -1000; i < 1000; i++)
12     {
13         int tmp;
14         tmp = u * (upTime + i) - d * (downTime - i);
15         
16         if ( (upTime + i) >= 0 && (downTime - i) >= 0 )
17         {
18             if (tmp > 0 && tmp < min)
19             {
20                 min = tmp;
21             }
22             if (min < 0 && tmp > 0)
23             {
24                 min = tmp;
25             }
26         }
27         
28         if (min == 0 && tmp > 0)
29         {
30             min = tmp;
31         }
32         
33     }
34     return min;
35 }
36 
37 int main()
38 {
39     int n;
40     int m;
41     while ( cin >> n )
42     {
43         cin >> m;
44         int lowest;
45         int up,down;
46         cin >> up >> down;
47         lowest = CCalLowest(up, down, n);
48         for (int i = 1; i < m; i++)
49         {
50             cin >> up >> down;
51             int tmp = CCalLowest(up, down, n);
52             if (tmp < lowest)
53             {
54                 lowest = tmp
55                 ;
56             }
57         }
58         
59         cout << lowest << endl;
60     }
61     return 0;
62 }
63 
64 // end 
65 // ism