[NOIp 2012]国王游戏

Description

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

Input

第一行包含一个整数 n，表示大臣的人数。

第二行包含两个整数 a和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

Output

输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

Sample Input

Sample Output

HINT

【输入输出样例说明】

按 1、2、3 号大臣这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按 1、3、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按 2、1、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按 2、3、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9；

按 3、1、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按 3、2、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9。

因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。

【数据范围】

对于 20%的数据，有 1≤ n≤ 10，0 < a、b < 8；

对于 40%的数据，有 1≤ n≤20，0 < a、b < 8；

对于 60%的数据，有 1≤ n≤100；

对于 60%的数据，保证答案不超过 10^9；

对于 100%的数据，有 1 ≤ n ≤1,000，0 < a、b < 10000。

题解

贪心部分:

对于第 $i$个大臣和第 $j$ 个大臣:

如果第 $i$ 个大臣放第 $j$ 个大臣前面对答案的贡献小些,那么第 $i$ 个大臣就放第 $j$ 个大臣前面

所以就是使 $a[i].x/a[j].y<a[j].x/a[i].y$

所以就是$a[i].x*a[i].y<a[j].x*a[j].y$

乘法部分相当于高精度乘低精度

除法部分相当于高精度除低精度

代码打得想学Python，但差不多算一遍过吧...

 //It is made by Awson on 2017.10.17

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <stack>

 #include <queue>

 #include <vector>

 #include <string>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Abs(x) ((x) < 0 ? (-(x)) : (x))

 using namespace std;

 const int N = ;

 int n, a, b;

 struct tt {

     int x, y;

     bool operator < (const tt &b) const{

         return x*y < b.x*b.y;

     }

 }w[N+];

 struct BIG_NUM {

     int a[], lenth;

     BIG_NUM () {

         memset(a, , sizeof(a)); a[] = lenth = ;

     }

     BIG_NUM (int* _a, int _lenth) {

         for (int i = ; i <= _lenth; i++) a[i] = _a[i]; lenth = _lenth;

     }

     BIG_NUM operator * (const int &b) const{

         BIG_NUM ans; ans.a[] = , ans.lenth = lenth;

         for (int i = ; i <= lenth; i++) ans.a[i] = a[i]*b;

         for (int i = ; i <= ans.lenth; i++) ans.a[i+] += ans.a[i]/, ans.a[i] %= ;

         while (ans.a[ans.lenth+]) ans.lenth++, ans.a[ans.lenth+] += ans.a[ans.lenth]/, ans.a[ans.lenth] %= ;

         return ans;

     }

     BIG_NUM operator / (const int &b) const{

         BIG_NUM ans; ans.a[] = , ans.lenth = lenth; int sum = ;

         while (sum < b) sum = sum*+a[ans.lenth--];

         for (int i = ans.lenth; i >= ; i--)

             ans.a[i+] = sum/b, sum = (sum%b)*+a[i];

         ans.a[] = sum/b, ans.lenth++;

         return ans;

     }

     bool operator < (const BIG_NUM &b) const{

         if (lenth < b.lenth) return true;

         else if (lenth > b.lenth) return false;

         for (int i = lenth; i >= ; i--)

             if (a[i] < b.a[i]) return true;

             else if (a[i] > b.a[i]) return false;

         return false;

     }

 }tmp, ans;

 void work() {

     scanf("%d%d%d", &n, &a, &b);

     for (int i = ; i <= n; i++) scanf("%d%d", &w[i].x, &w[i].y);

     sort(w+, w++n);

     tmp = tmp*a;

     for (int i = ; i <= n; i++) {

         BIG_NUM tmpp = tmp/w[i].y;

         if (ans < tmpp) ans = tmpp;

         tmp = tmp*w[i].x;

     }

     for (int i = ans.lenth; i >= ; i--) printf("%d", ans.a[i]);

 }

 int main() {

     work();

     return ;

 }

秒客网