Sol.

前言

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

分析

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

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

如果你想 dfs 的话，对不起，TLE！

O(2^n)

的复杂度，对于

n \leq 10^6

的数据，还是多测的情况下，跑到世界末日都跑不完。~~（如果你是剪枝 dalao 当我没说）~~

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

维护

3

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

2

的数量。

由题可知，

执行操作 $1$ 后总和与野兽总数均增加（平均值增加的数量可忽略不计）
执行操作 $2$ 后总和不变，野兽总数减少，平均值增加。

因此，只要尽可能执行操作

2

就可以最大化平均值，如果野兽总数不够就减少一次执行的操作

2

。

Code

CPP

#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

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

文章操作

Sol.

前言

分析

Code

相关推荐

评论

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