P1080 国王游戏
题解
贪心策略：按照大臣左右手数字乘积从小到大排序
假设我们已经把大臣排了一个顺序
假定在这个顺序下我们可以保证 得到奖赏最多的大臣所得奖赏最少
那么我们一旦交换任意两个大臣，得到奖赏最多的大臣所得奖赏就不是最少的
假设 3,4 号大臣是候选 “ 所得奖赏最多的大臣 ” ，那么我们现在交换他们的顺序
交换之后 3,4 之前的大臣以及3,4之后的大臣所得奖赏都不会被影响，受到影响的只是3,4号大臣
那么我们设3,4之前的大臣左手上的乘积和为 S
所以，
对于交换前：ans1 = max( s / b[3] , s * a[3] / b[4] )
对于交换后：ans2 = max( s / b[4] , s * a[4] / b[3] )
由于交换后无法得到更优解，所以
ans1 < ans2
max( s / b[3] , s * a[3] / b[4] ) < max( s / b[4] , s * a[4] / b[3] )
max( 1 / b[3] , 1 * a[3] / b[4] ) < max( 1 / b[4] , 1 * a[4] / b[3] )
所以答案只和第2,4项有关
a[3] / b[4] < a[4] / b[3]
移项
a[3] * b[3] < a[4] * b[4]
所以：
贪心策略：按照大臣左右手数字乘积从小到大排序
剩下的问题就是高精度处理了QWQ
代码
#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> using namespace std; #define ll long long inline int read() { int ans=0; char last=' ',ch=getchar(); while(ch<'0'||ch>'9') last=ch,ch=getchar(); while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar(); if(last=='-') ans=-ans; return ans; } int n; long long ans; struct node { int a,b; long long val; long long mul; }peo[1005]; bool cmp(node x,node y) { return x.mul <y.mul ; } int main() { n=read(); for(int i=0;i<=n;i++) { peo[i].a =read(); peo[i].b =read(); peo[i].mul =peo[i].a *peo[i].b ; } sort(peo+1,peo+n+1,cmp); for(int i=1;i<=n;i++) { long long res=1; for(int j=0;j<i;j++) res*=peo[j].a ; res/=peo[i].b ; ans=max(ans,res); } printf("%lld\n",ans); return 0; }