题解：P14159 [ICPC 2022 Nanjing R] 邪恶铭刻

· · 题解

Sol.

题目链接

前言

简单贪心题，与 CSP-J 2023 T2 一样都属于反悔贪心题。

分析

蒟蒻一眼看去，还以为是 DP，但经过我不信邪坚持不懈的分析后，发现是一道贪心题。（好吧其实是蒟蒻不会 DP）

题目 blabla 说了一大串，实际上就是让我们在 2 中决策的左右横跳中求最大值。

如果你想 dfs 的话，对不起，TLE！O(2^n) 的复杂度，对于 n \leq 10^6 的数据，还是多测的情况下，跑到世界末日都跑不完。（如果你是剪枝 dalao 当我没说）

因此，需要使用线性算法来解决。

维护 3 个变量，分别记录当前的攻击力总和，野兽先辈总数和在岔路口执行操作 2 的数量。

由题可知，

因此，只要尽可能执行操作 2 就可以最大化平均值，如果野兽总数不够就减少一次执行的操作 2。

Code

#include <bits/stdc++.h>

using namespace std;

int t;
int n;

int main() {
    scanf("%d", &t);

    while (t--) {
        scanf("%d", &n);
        int sum = 1;
        int now = 1, ls = 0;
        bool canr = true; // now：野兽总数，ls：执行操作 2 的数量，sum：攻击力总和

        for (int i = 1; i <= n; i++) {
            int a;
            scanf("%d", &a);
            if (a == 1) {
                now++;
                sum++;
            } else if (a == -1) {
                if (now > 1) {
                    now--;
                } else {
                    if (ls == 0) {
                        canr = false;
                    } else {
                        sum++;
                        now++;
                        ls--;
                    }
                }
            } else {
                if (now < 2) {
                    now++;
                    sum++;
                } else {
                    now--;
                    ls++;
                }
            }
        }

        if (!canr) printf("-1");
        else {
            int gcd = __gcd(sum, now);
            printf("%d %d", sum / gcd, now / gcd);
        }
        printf("\n");
    }

    return 0;
}

AC 记录

求过 QWQ