[NOIP 2012 提高组] 国王游戏

知识点

贪心排序、交换论证、高精度

解题思路

将大臣按左手×右手的乘积升序排列。维护前方左手数的高精度乘积，每到一人先除以其右手数更新最大奖赏，再乘其左手数。

正确性说明

相邻两人左右手为(a,b)、(c,d)，前缀乘积为P。两种顺序奖赏最大值分别是max(floor(P/b),floor(Pa/d))与max(floor(P/d),floor(Pc/b))。若ab≤cd，交换为前者不会增大上界：Pa/d≤Pc/b；且P/b≤Pc/b（c≥1）。故前者不超过后者。反复交换逆序对得到乘积升序最优。其他人的前缀乘积不变。

易错点

国王不能排序；先计算奖赏再乘当前左手；右手只参与除法；乘积可有数千位。

复杂度

排序O(n log n)，随后n次小整数高精度乘除；空间与累计乘积位数成正比。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct Big{static const int B=10000;vector<int>d;Big(long long x=0){do{d.push_back(x%B);x/=B;}while(x);}void trim(){while(d.size()>1&&d.back()==0)d.pop_back();}bool operator<(const Big&o)const{if(d.size()!=o.d.size())return d.size()<o.d.size();for(int i=(int)d.size()-1;i>=0;i--)if(d[i]!=o.d[i])return d[i]<o.d[i];return false;}Big operator+(const Big&o)const{Big r;r.d.assign(max(d.size(),o.d.size())+1,0);int carry=0;for(int i=0;i<(int)r.d.size();i++){int v=carry+(i<(int)d.size()?d[i]:0)+(i<(int)o.d.size()?o.d[i]:0);r.d[i]=v%B;carry=v/B;}r.trim();return r;}Big operator*(const Big&o)const{vector<long long>v(d.size()+o.d.size()+1);for(int i=0;i<(int)d.size();i++)for(int j=0;j<(int)o.d.size();j++)v[i+j]+=1LL*d[i]*o.d[j];Big r;r.d.resize(v.size());for(int i=0;i<(int)v.size();i++){if(i+1<(int)v.size())v[i+1]+=v[i]/B;r.d[i]=v[i]%B;}r.trim();return r;}Big operator*(int x)const{return *this*Big(x);}Big operator/(int x)const{Big r=*this;long long rem=0;for(int i=(int)d.size()-1;i>=0;i--){long long v=rem*B+d[i];r.d[i]=v/x;rem=v%x;}r.trim();return r;}friend ostream&operator<<(ostream&os,const Big&a){os<<a.d.back();for(int i=(int)a.d.size()-2;i>=0;i--)os<<setw(4)<<setfill('0')<<a.d[i];return os;}};

int main(){int n,a,b;cin>>n>>a>>b;Big prod(a),best;vector<pair<int,int>>v(n);for(auto&x:v)cin>>x.first>>x.second;sort(v.begin(),v.end(),[](auto x,auto y){return 1LL*x.first*x.second<1LL*y.first*y.second;});for(auto[x,y]:v){Big gain=prod/y;if(best<gain)best=gain;prod=prod*x;}cout<<best<<'\n';}