国王 游戏

ybtoj 贪心-1-4

题目大意

有一个国王和n个大臣
每人左右手分别有一个数，现在然你对大臣们排列（国王在第一个）
每个大臣所得金币是前面的人左手上的数的积除以他右手上的数
现在问你获得金币最多的大臣最少得多少金币

样例输入

样例输出

数据范围

考虑交换相邻的大臣
设 $s_i$ 为前i个大臣左手的数字之积
如果交换第i，i+1个大臣，那么有：

	第i个大臣	第i+1个大臣
交换前	$si−1ri\frac{s_{i-1}}{r_i}$	$si−1×liri+1\frac{s_{i-1}\times l_i}{r_{i+1}}$
交换后	$si−1ri+1\frac{s_{i-1}}{r_{i+1}}$	$si−1×li+1ri\frac{s_{i-1}\times l_{i+1}}{r_i}$

所取到的最大值分别是 $max(si−1ri,si−1×liri+1)max(\frac{s_{i-1}}{r_i},\frac{s_{i-1}\times l_i}{r_{i+1}})$ 和 $max(si−1ri+1,si−1×li+1ri)max(\frac{s_{i-1}}{r_{i+1}},\frac{s_{i-1}\times l_{i+1}}{r_i})$
同时除以 $s_{i-1}$
得到 $max(1ri,liri+1)，max(1ri+1,li+1ri)max(\frac{1}{r_i},\frac{l_i}{r_{i+1}})，max(\frac{1}{r_{i+1}},\frac{l_{i+1}}{r_i})$
同时乘 $ri×ri+1r_i\times r_{i+1}$
得到 $max(ri+1,ri×li),max(ri,ri+1×li+1)max(r_{i+1},r_i\times l_i),max(r_i,r_{i+1}\times l_{i+1})$
其中 $ri+1⩽ri+1×li+1,ri⩽ri×lir_{i+1}\leqslant r_{i+1}\times l_{i+1},r_i\leqslant r_i\times l_i$
若 $ri+1×li+1⩾ri×lir_{i+1}\times l_{i+1}\geqslant r_i\times l_i$
则 $ri+1×li+1⩾max(ri+1,ri×li),r_{i+1}\times l_{i+1}\geqslant max(r_{i+1},r_i\times l_i),$
所以 $r_{i+1}$ 没有判断的价值， $r_i$ 同理
所以可以直接对 $l×rl\times r$ 来进行判断考虑是否交换
~~综上所述~~，对 $l×rl\times r$ 排个序，然后高精处理即可

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n, x, y, g, a[4020], b[4020], ans[4020];
struct node
{ll x, y;bool operator <(const node b) const{return x * y > b.x * b.y;//排序}
};
priority_queue<node>d;
int main()
{scanf("%lld%lld%lld", &n, &x, &y);g = 1;while(x){b[g] = x % 10;x /= 10;g++;}for (int i = 1; i <= n; ++i) {scanf("%lld%lld", &x, &y);d.push((node){x, y});}while(!d.empty()){node h = d.top();d.pop();g = 0;for (int i = 4010; i > 0; --i){a[i] = (b[i] + g * 10) / h.y;g = (b[i] + g * 10) % h.y;//前面的l除以当前的r}g = 0;for (int i = 4010; i > 0; --i)if (a[i] > ans[i])//取最大值{g = i;break;}else if (a[i] < ans[i]) break;for (int i = 1; i <= g; ++i)ans[i] = a[i];g = 0;for (int i = 1; i <= 4010; ++i){b[i] = b[i] * h.x + g;//乘上lg = b[i] / 10;b[i] %= 10;}}g = 4010;while(g > 1 && !ans[g]) g--;for (int i = g; i > 0; --i)putchar(ans[i] + 48);return 0;
}