国王游戏
题目描述:
恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输入格式:
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数 a和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式:
输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
样例输入:
3 1 1 2 3 7 4 4 6
样例输出:
2
提示:
【输入输出样例说明】
按 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。
时间限制:1000ms
空间限制:256MByte
来源:NOIP2012提高t2
初看此题，居然没有第一时间反应过来这居然是贪心（只是想练练高精而已TAT），结果想了好久才发现可以贪❤，然后加个高精乘除比较就好了。
下面证明一下贪心的正确性：
我们设第i个大臣左手是a[ i ] , 右手是b[ i ] ， w[i]代表a[ 1 ] * a[ 2 ] * a[ 3 ] * ... * a[ i ] ， val[ i ] 代表这第i个大臣可以获得的钱数；
不难发现 ， val [ i ] = w[ i - 1 ] / b [ i ] ， val [ i + 1 ] = w[ i ] / b [ i + 1 ];
应为w[ i ] = w [ i - 1 ] * a [ i ];
所以 val [ i + 1 ] = w[ i ] / b [ i + 1 ] = w [ i - 1 ] * a [ i ] / b [ i + 1 ];
将这两条式子相除
val [ i ] = w[ i - 1 ] / b [ i ] ;
val [ i + 1 ] = w[ i ] / b [ i + 1 ] = w [ i - 1 ] * a [ i ] / b [ i + 1 ];
得到： val [ i ] / val[ i + 1 ] = b [ i + 1 ] / (b [ i ] * a [ i ]);
移项得到： val[ i + 1] = a [ i ] * b [ i ] * val [ i ] / b[ i + 1 ];
应为b[ i + 1 ]是固定的，所以val[ i + 1]的大小只和a [ i ] * b [ i ] * val [ i ]有关系；
现在考虑让val[ i + 1 ] 最小，应为前面i个已知，所以val[ i ]是确定的。
所以为了让val[ i + 1 ]最小，就要让a[ i ] * b[ i ]小；
所以只要在（1 ~ i）之间用a[ i ] * b[ i ]排序就好啦；
推广到整个队列就也这样排序；
#include<cstdio> #include<cstring> #include<iostream> #include<iomanip> #include<algorithm> #define ll long long #define _ 8 #define mod 100000000 #define maxn 10050 using namespace std; struct bg{ ll v[maxn]; int size; bg(){ memset(v,0,sizeof(v)); } }; struct st{ int a,b; ll val; }s[maxn]; bool com(st a , st b) { return a.val < b.val; } inline bool operator <(bg a , bg b) { if(a.size < b.size) return 1; if(a.size > b.size) return 0; for(int i=a.size;i>=1;i--) { if(a.v[i] < b.v[i]) return 1; if(a.v[i] > b.v[i]) return 0; } return 0 ; } inline ostream& operator <<(ostream &os , bg x) { ll i; os << x.v[x.size]; for(int i=x.size - 1;i;i--) os << setfill('0') << setw(_) << x.v[i]; return os; } inline bg operator *(bg a , ll b) { for(int i=1;i<=a.size;i++) a.v[i] *= b; ll jin = 0; for(int i=1;i<=a.size;i++) { a.v[i] += jin; jin = a.v[i] / mod; a.v[i] %= mod; } while(jin) { a.v[++a.size] = jin % mod; jin /= mod; } return a; } inline bg operator /(bg a , ll b) { ll rest = 0 , pos = a.size , len = a.size; while(rest < b && pos) { rest = rest * mod + a.v[pos]; pos--; } pos++; bg c; if(pos == 1 && rest < b) return c; c.size = pos; while(pos) { c.v[pos] = rest / b; rest %= b; pos--; rest = rest * mod + a.v[pos]; } if(!c.v[c.size]) c.size--; return c; } int n; bg ans,ma; int main(){ // freopen("testdata.in","r",stdin); scanf("%d",&n); for(int i=0;i<=n;i++) scanf("%d%d",&s[i].a,&s[i].b),s[i].val = s[i].a * s[i].b; sort(s+1,s+1+n,com); ans.size = 1; ans.v[1] = 1; ans = ans * s[0].a; for(int i=1;i<=n;i++) { if(ma < (ans / s[i].b)) ma = (ans / s[i].b); ans = ans * s[i].a; } cout << ma <<endl; }