D14562. 【NOIP2012T】国王游戏

时间限制：1.0s 内存限制：128.0MB

输入文件名：game.in 输出文件名：game.out

试题来源：NOIP

问题描述

　　恰逢 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%的数据,保证答案不超过 109;

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

　　

思路

先看出来这是一个全排列，按照方法深搜全排列出大臣的顺序求解。算法复杂度高苟得20分。

按照搜索的结果测试数据规律，在小数据中根本看不出来，然后输入一些比较大的值才看出。

贪心策略：设左右手数字为Li和Ri，则优先选择Li*Ri更大的大臣优先领奖。如此取得最优解。

贪心证明：设当前有两人AB,左右手数分别为Al,Ar,Bl,Br，且Al < Bl。前各项乘积为W。两个人位置互换时并不会影响W的值，而后续乘积为W * AL * BL，所以我们暂且讨论这两人。当前若A在前 ，

则ans1=max( w / Ar, w * Al / Br) , 反之ans2 = max(w / Br, w * Bl / Ar)。

易知w / ar < w * bl / ar,同理w / br <　w * al / br

当ans1 < ans2 时，有w * bl / ar > w * al/ br,化简得到ar * al < br 　bl ,即当ar al乘积小时会产生局部最优解，符合最优解子结构。贪心策略正确。

在具体实现时，单个AB的值就到10000，要使用高精度。

时先是数组开小导致超时（数组小可能会导致TLE），开大以后莫名出现运行错误，恩是重载运算符直接复制模板，但是这个模板存在错误（这个模板是WTS教授的），然后重写了一个高精度重载运算符后通过。

Code:

#include
    
     using namespace std;int n, a, b;struct bign  {   int d[41000],len;   bign operator = (const int num){      char s[41000];      sprintf(s,"%d",num);      *this=s;      return *this;   }   bign operator = (const string st){      memset(d,0,sizeof(d));      int lst=st.size();      len=lst;      for(int i=0;i
     
      0){         ans.len++;         ans.d[ans.len]=g;         g=ans.d[ans.len]/10;         ans.d[ans.len]%=10;      }      return ans;   }   bign operator / (int x){      bign ans;      memset(ans.d,0,sizeof(ans.d));      int cnt=0;int t[41000];memset(t,0,sizeof(t));      int g=0;      bool flag=false;      for(int i=len;i>=1;i--){         g=g*10+d[i];         if(g>=x){            flag=true;            t[++cnt]=g/x;            g=g%x;         }         else if(flag){            t[++cnt]=0;         }      }      ans.len=cnt;      for(int i=1;i<=cnt;i++)         ans.d[ans.len-i+1]=t[i];      if(cnt==0){         ans.len=1;         ans.d[ans.len]=0;      }      return ans;   }   bool operator < (const bign& b) const {      if(len!=b.len)return len
      
       =1;i--)         if(d[i]!=b.d[i])return d[i]
       
        > n;    cin >> a >> b;    for (int i = 1; i <= n; i++)        cin >> ofr[i].l >> ofr[i].r;    sort(ofr + 1, ofr + n + 1, cmp);    bign blank, ans, gift;    blank = 1 * a;//高精度累计计算并统计最大值。    for (int i = 1; i <= n; i++) {        gift = blank / ofr[i].r;        blank = blank * ofr[i].l;        if (ans < gift) ans = gift;    }    cout << ans << endl;    return 0;}