CF1635B 题解

liangbowen · 2022-04-20 09:12:42 · 题解

题目传送门！

更好的阅读体验？

这题显然可以使用贪心的思想解决。

由于头和尾一定不用更改，所以只需从 a_2 枚举到 a_{n-1}。

贪心原则下，我们更改的数应该要与相邻的数相等。

按照上面的原则，如果你更改了 a_i，则下一个可能需要更改的数至少是 a_{i+2}。

所以，如果此时 a_i 不满足要求，你应该更改 a_{i+1}。

代码如下，时间复杂度 O(n)。

完整代码

#include <iostream>
#include <cstdio>
using namespace std;
int a[200005];
void solve()
{
    int n, cnt = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 2; i < n; i++)  //头和尾肯定不用改。
        if (a[i] > a[i-1] && a[i] > a[i+1])
            cnt++, a[i+1] = max(a[i], a[i+2]);
    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    printf("\n");
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}