国王游戏_(贪心)

原题链接：P1080 [NOIP2012 提高组] 国王游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：国王邀请大臣发奖金，国王排在最前面，大臣排序不定，每个人左右手各写一个数字，每个人的奖金是前面所有人左手上数字的乘积除以自己右手的数字，此时希望拿到最多奖金的大臣不要拿太多，即最大的最小，求这个值是多少

思路

其实想到但无法证明

首先，对贪心最重要的是证明的思路，这道题采用的是思路化简，就从两个大臣来看，再扩展到任意大臣

大臣A，大臣B，国王N 大臣A左手数字Aa，右手数字Ab，大臣B左手数字Ba，右手数字Bb

如果大臣A在B前面，那么二人的奖金分别是 A：Na / Ab B：Na * Aa / Bb 如果位置互换 A：Na * Ba / Ab B：Na / Bb

对于A来说，两种情况Ap_1⇐Ap_2 对于B来说，两种情况Bp_1>=Bp_2

要二者奖金最大的最小，就要对比Ap_2和Bp_1

如果排序要A在B前面，就得满足

$$Na\ast Ba/Ab>Na\ast Aa/Bb$$

即

$$Ba\ast Bb>Aa\ast AbA,B>0$$

就是说 a * b 大的排在后面，按这个顺序排每两个人收到的奖金最大值就最大

如果多个人呢？首先这两个人的排序对之前人的最大奖金没有影响，对之后人的最大奖金也没有影响，也就是如果每每两人都遵循这种排序，那么奖金最大就会最小

高精度

这道题还需要有高精度乘除法的实现，废物还是不会默写，至少理解理解吧

代码

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1024;
 
struct DC{
    int a, b;
    vector<int> ans;
    vector<int> sum;
}dc[N];
 
bool cmp(DC x, DC y)
{
    return x.a * x.b < y.a * y.b;
}
 
vector<int> cmp_h(vector<int> x, vector<int> y)
{
    if(x.size() > y.size())
        return x;
    else if(x.size() < y.size())
        return y;
    else
    {
        for(int i = x.size(); i >= 0; i --)
        {
            if(x[i] > y[i]) return x;
            if(x[i] < y[i]) return y;
        }
 
        return x;
    }
}
 
vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size() || t != 0; i ++)
    {
        if(i < a.size()) t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
 
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
 
vector<int> div(vector<int> &a, int b)
{
    vector<int> c;
    int r = 0;
    for(int i = a.size() - 1; i >= 0; i --)
    {
        r = r * 10 + a[i];
        c.push_back(r / b);
        r %= b;
    }
 
    reverse(c.begin(), c.end());
    while(c.size() > 1 && c.back() == 0) c.pop_back();
 
    return c;
}
 
 
int n;
int ga, gb;
 
int main()
{
    cin >> n;
    cin >> ga >> gb;
    for(int i = 0; i < n; i ++)
    {
        cin >> dc[i].a >> dc[i].b;
    }
 
    sort(dc, dc + n, cmp);
 
    vector<int> ini;
    ini.push_back(1);
 
    dc[0].sum = mul(ini, ga);
    dc[0].ans = div(dc[0].sum, dc[0].b);
 
    vector<int> res = dc[0].ans;
 
    for(int i = 1; i < n; i ++)
    {
        dc[i].sum = mul(dc[i-1].sum, dc[i-1].a);
        dc[i].ans = div(dc[i].sum, dc[i].b);
 
        res = cmp_h(res, dc[i].ans);
    }
 
    for(int i = res.size() - 1; i >= 0; i --)
    {
        cout << res[i];
    }
    cout << endl;
 
    return 0;
}