AcWing 耍杂技的牛(国王游戏) 2021第一篇题解

国王游戏网上的题解已经够多了,这里贴上我艰难地写出的代码,之后讲解一个使用相同思想但实现起来简单得多的题目.

// 国王游戏
// 高精度写得并不完善, 精力所限没有继续追究
// 我的高精度总结:https://www.cnblogs.com/Gaomez/p/14198544.html

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef pair<int, int> PII;
int n, cur[5000], curtmp[5000], ans[5000], tmp[5000], lena = 0, lenc = 1, lent = 1;
PII s[1010];

int mul1(int x, int l) {
    memset(tmp, 0, sizeof(tmp));

    for (int i = 1; i <= l; i++) tmp[i] = cur[i] * x;
    
    for (int i = 1; i < 4999; i++) {
        tmp[i + 1] += tmp[i] / 10;
        tmp[i] %= 10;
    }
    l = 4999;
    while(!tmp[l] && l) l--;
    l = (l ? l : 1);
    for (int i = 1; i <= 4999; i++) cur[i] = tmp[i];
    return l;
}

int div1(int x, int l) {
    memset(tmp, 0, sizeof(tmp));
    memcpy(curtmp, cur, sizeof(cur));

    for (int i = l; i >= 1; i--) {
        tmp[i] = curtmp[i] / x;
        curtmp[i - 1] += (curtmp[i] % x) * 10;
    }
    while (!tmp[l] && l) l--;
    l = (l ? l : 1);
    for (int i = l; i >= 1; i--) curtmp[i] = tmp[i];

    return l;
}

void cmp() {
    bool big = false;

    if (lent != lena)
        big = lent > lena;
    else
        for (int i = lent; i >= 1; i--)
            if (ans[i] != curtmp[i]) {
                big = curtmp[i] > ans[i];
                break;
            }
    if (big) {
        for (int i = lent; i >= 1; i--) ans[i] = curtmp[i];
        lena = lent;
    }
}

int main() {
    int a, b;
    scanf("%d", &n);
    for (int i = 0; i <= n; i++) {
        scanf("%d%d", &a, &b);
        s[i] = {a * b, b};
    }

    cur[1] = 1;
    curtmp[1] = 1;
    lenc = mul1(s[0].first / s[0].second, lenc);
    sort(s + 1, s + 1 + n);

    for (int i = 1; i <= n; i++) {
        lent = div1(s[i].second, lenc);  // curtmp = cur, curtmp /= b
        cmp();                           // cur_tmp > ans ?
        lenc = mul1(s[i].first / s[i].second, lenc);  // cur *= a / b
    }

    int head = 4999;
    while (!ans[head] && head) head--;
    head = (head ? head : 1);
    for (int i = head; i >= 1; i--) printf("%d", ans[i]);
    putchar('
');

    return 0;
}

(注意理解题意,最高处的牛也要算上,它头上的总重量是0)

假设有如下的奶牛堆叠:(括号内分别表示W,S)

①

(e,f)

(c,d)

(a,b)

②

(e,f)

(a,b)

(c,d)

这两种方式区别在于下面两头奶牛的位置相反,现在讨论一下哪种情况下更优.

设最大风险值为D.

①D=max{e-d, e+c-b}.

②D=max{e-b, e+a-d}.

可见两种情况下最大风险值都不会受到牛(e,f)的影响,牛(e,f)及其以上所有的牛在这里都可以合成为一头牛,不妨设e=0,就可以排除所有其它牛的干扰.

①D=max{-d, c-b}.

②D=max{-b, a-d}.

现在想要找到哪种情况下可以取得更小的D,注意到交叉项有-d<a-d, -b<c-b,

如果假设情况①优于情况②,即max{-d, c-b} < max{-b, a-d},

若左边取得-d,右边>=a-d,不等式一定成立;

若左边取得c-b,右边只有取a-d时可能成立,成立时有c-b < a-d, 即当且仅当c + d < a + b时情况①优于情况②.

所以将所有的牛按照w+s的大小为关键字进行排序即可,大者在下,这与直观的逻辑是符合的:重量越大,力量越大越应该在下面.

 相比于国王游戏,这题不需要高精度,实现起来简单得多.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n;
long long ans = -1e18, sum;
pair<int, int> p[50010];

int main(){
    int w, s;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &w, &s);
        p[i] = {w + s, s};
    }
    if(n == 1){
        printf("%d", -p[1].second);
        return 0;
    }
    sort(p + 1, p + 1 + n);

    for(int i = 0; i < n; i++){
        sum += p[i].first - p[i].second;
        ans = max(ans, sum - p[i + 1].second);
    }

    printf("%lld
", ans);

    return 0;
}