Posted in日常

P1080-国王游戏

2024年3月29日

题目传送门

点我

题目思路

本质上是贪心加高精度，确定做法后很简单。给出贪心的证明

根据题意我们可以知道，大臣1和大臣2位置能交换的必要条件是：大臣2放在大臣1的前面得到的最大值更加小。那么我们分别讨论两种情况下的最大值，假设只有两个大臣：
如果大臣1放在前面，他俩获得的金币数分别为：
	a0/b1,a0*a1/b2
如果大臣2放在前面，他俩获得的金币数分别为：
	a0/b2,a0*a2/b1
首先，我们约去式子里面的a0，然后分别讨论两种情况的最大值，就变成了比较：
	max(1/b1,a1/b2)和max(1/b2,a2/b1)的大小
根据0<a，a是整数的条件，我们可以得出: 
	a1/b2 >= 1/b2、1/b1 <= a2/b1
    
那么，如果1/b1是最大的，则有
	1/b1>=a2/b1，只可能左右两边相等，则有1/b2<=a2/b1，所以两种情况的最大值是一样的，则不用交换。
同理可得1/b2是最大的情况也不用交换。
那么我们就只要a1/b2和a2/b1的大小就可以了，也就是说如果a1/b2>a2/b1，那么就要交换，变形得：
	a1*b1 > a2*b2
表示要交换，我们排序就只要按照a*b的从小到大排就可以了。

再补充一下贪心的使用条件：

贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。

  1. 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
  2. 归纳法：先算得出边界情况（例如 n=1）的最优解f1 ，然后再证明：对于每个n ， fn都可以由f1  推导出结果。

然后就是高精度的乘法和除，不得不说copilot太好用了。。我刚准备打板的时候它给我写好了。。。。

这样我怎么锻炼自己。。。。

AC代码

#include <bits/stdc++.h>

using namespace std;

class Node
{
public:
    int a;
    int b;
    int v;
    Node() : a(0), b(0), v(0) {}
    Node(int a, int b) : a(a), b(b), v(a * b) {}
    bool operator<(const Node &n)
    {
        return v < n.v;
    }
};

string mul(string a, int b)
{
    string res;
    int carry = 0;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        int t = (a[i] - '0') * b + carry;
        res.push_back(t % 10 + '0');
        carry = t / 10;
    }
    while (carry)
    {
        res.push_back(carry % 10 + '0');
        carry /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

string div(string a, int b)
{
    string res;
    int carry = 0;
    for (int i = 0; i < a.size(); i++)
    {
        int t = (a[i] - '0') + carry * 10;
        res.push_back(t / b + '0');
        carry = t % b;
    }
    while (res.size() > 1 && res[0] == '0')
    {
        res.erase(res.begin());
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    int af, bf;
    cin >> af >> bf;
    vector<Node> a(n + 1);
    vector<string> res(n + 1);
    a[0] = Node(af, bf);
    res[0] = "1";
    for (int i = 1; i <= n; i++)
    {
        int aa, bb;
        cin >> aa >> bb;
        a[i] = Node(aa, bb);
    }
    sort(a.begin() + 1, a.end(), [](Node &a, Node &b)
         { return a < b; });

    string r = "1";
    for (int i = 1; i <= n; i++)
    {
        res[i] = mul(res[i - 1], a[i - 1].a);
        if (r.compare(div(res[i], a[i].b)))
        {
            r = div(res[i], a[i].b);
        }
    }
    cout << r << endl;

    return 0;
}
Tags: