Problem description
恰逢 H 国国庆,国王邀请n位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这n位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
Input format
第一行包含一个整数 n,表示大臣的人数。
第二行包含两个整数 a 和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数。
接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。
Output format
输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
Algorithm design
贪心算法
Problem analysis
直接模拟最多采用全排列+记忆化，效率极低，算法很明显是贪心
贪心可以说是目前最难的一个模块了，因为要考验最优解子结构分析
一开始直接想全局放置的方式，想破头也没有想出来
老师说对于线性贪心可以先考虑两两之间的关系，就取相邻两个大臣突破
很容易发现：
令臣a在臣b前，设之前乘积为S，则臣a收益S/ra，臣b收益S*la/rb
反之，臣a收益S*lb/ra,臣b收益S/rb
通分一下，情况1为max(rb,la*ra)，情况2为max(ra,lb*rb)
分情况讨论：
（1）la*ra>rb,lb*rb>ra,则li*ri的大小决定了位置（越大越后）
（2）la*ra<rb,因为lb>=1,所以lb*rb>la*ra，且b应该放在a后，不悖结论1
（3）lb*rb<ra,因为la>=1，所以la*ra>lb*rb,且a应该放在b后，不悖结论1
故结论1成立，li*ri越大的臣子越靠后可以使解最优，则进行以li*ri为关键字的排序即可
排序完之后，必定保证金币数从小到大递增，且最后一人为最小的最大值
用这个算法仅过了60，不难发现，数据达到10000时金币可能为10000^10000
这是一个非常庞大的数字，所以想到高精度乘法，除法
码完高精度成绩没有丝毫改观，调试后发现是重载运算符数组开小了，由前面的结论得，至少要开到40000的空间，当不小心开成400000的时候，程序会超时最后这个代码还是90分的，原因是此贪心法则只能保证结果最小，而非最后臣子为最大值，所以ans应该中途更新
Source code
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 struct bign 6 { 7 int len,num[40010]; 8 void clean() 9 { 10 while(len>1&&!num[len-1]) 11 len--; 12 } 13 bign operator =(string st) 14 { 15 memset(num,0,sizeof(num)); 16 len=st.size(); 17 for(int i=0;i<len;i++) 18 num[i]=st[len-i-1]-'0'; 19 return *this; 20 } 21 bign operator =(bign n) 22 { 23 memset(num,0,sizeof(num)); 24 len=n.len; 25 for(int i=0;i<len;i++) 26 num[i]=n.num[i]; 27 return *this; 28 } 29 bign operator +(bign n) 30 { 31 bign ans; 32 memset(ans.num,0,sizeof(ans.num)); 33 ans.len=max(len,n.len); 34 int accu=0; 35 for(int i=0;i<ans.len;i++) 36 { 37 int res=num[i]+n.num[i]+accu; 38 ans.num[i]=res%10; 39 accu=res/10; 40 } 41 if(accu)ans.num[ans.len++]=accu; 42 return ans; 43 } 44 bign operator +=(bign n) 45 { 46 *this=*this+n; 47 return *this; 48 } 49 bign operator *(int n) 50 { 51 bign ans; 52 memset(ans.num,0,sizeof(ans.num)); 53 ans.len=len; 54 for(int i=0;i<ans.len;i++) 55 ans.num[i]=num[i]*n; 56 int accu=0; 57 for(int i=0;i<ans.len;i++) 58 { 59 ans.num[i]+=accu; 60 accu=ans.num[i]/10; 61 ans.num[i]%=10; 62 } 63 while(accu)ans.num[ans.len++]=accu%10,accu/=10; 64 ans.clean(); 65 return ans; 66 } 67 bign operator *=(int n) 68 { 69 *this=*this*n; 70 clean(); 71 return *this; 72 } 73 bign operator /(int n) 74 { 75 bign ans; 76 memset(ans.num,0,sizeof(ans.num)); 77 ans.len=len; 78 int res=0; 79 for(int i=ans.len-1;i>=0;i--) 80 { 81 res=res*10+num[i]; 82 ans.num[i]=res/n; 83 res%=n; 84 } 85 while(ans.num[ans.len-1]==0&&ans.len>1)ans.len--; 86 ans.clean(); 87 return ans; 88 } 89 bign operator /=(int n) 90 { 91 *this=*this/n; 92 clean(); 93 return *this; 94 } 95 bool operator <(bign n) 96 { 97 if(n.len>len)return 1; 98 if(n.len<len)return 0; 99 for(int i=len-1;i>=0;i--) 100 if(num[i]<n.num[i]) 101 return 1; 102 else if(num[i]>n.num[i]) 103 return 0; 104 return 0; 105 } 106 friend ostream& operator <<(ostream& out ,bign n) 107 { 108 for(int i=n.len-1;i>=0;i--) 109 out<<n.num[i]; 110 return out; 111 } 112 }; 113 114 int n; 115 bign res,ans; 116 117 struct node 118 { 119 int l,r; 120 }hand[10010]; 121 122 bool cmp(node p,node q) 123 { 124 if(p.l*p.r==q.l*q.r)return p.l<q.l; 125 return p.l*p.r<q.l*q.r; 126 } 127 128 int main() 129 { 130 freopen("game.in","r",stdin); 131 freopen("game.out","w",stdout); 132 cin>>n; 133 for(int i=0;i<=n;i++) 134 cin>>hand[i].l>>hand[i].r; 135 sort(hand+1,hand+n+1,cmp); 136 res="1"; 137 res*=hand[0].l; 138 for(int i=1;i<=n;i++) 139 { 140 bign wei; 141 wei=res/hand[i].r; 142 if(ans<wei) 143 ans=wei; 144 res*=hand[i].l; 145 }//中途过程更新出答案 146 cout<<ans<<endl; 147 return 0; 148 }
over