P10073 [GDKOI2024 普及组] 刷野 II 的题解

谨以此篇题解记录我考场上唯一通过的一题~

解题思路

可以考虑定义两个指针 x 和 y，分别为左侧攻击到哪里和右侧。此时，从两侧线性想中间递推，若先打左边的代价小就打左边的，否则就打右边的。按照这个方法向中间推就可以了。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 5e6 + 5;

void read(int &s)
{
    s = 0;
    char ch = getchar();
    char last = ch;

    while (ch < '0' || ch > '9')
        last = ch, ch = getchar();

    while (ch >= '0' && ch <= '9')
        s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();

    if (last == '-')
        s = -s;
}

int n;
int a[N];
int x, y;
int ans[N];
int t;

int main()
{
    read(t), read(n);

    for (int i = 1; i <= n; i++)
        read(a[i]);

    x = 1, y = n;

    while (x <= y)
    {
        int nx = max(a[x], ans[0] + 1), ny = max(a[y], ans[0] + 1);

        if (nx >= ny)
            ans[0] = ny, ans[n - y + x] = y, y--;
        else
            ans[0] = nx, ans[n - y + x] = x, x++;
    }

    printf("%d\n", ans[0]);

    for (int i = n; i; i--)
    printf("%d ", ans[i]);

    return 0;
}