这题显然可以使用贪心的思想解决。
由于头和尾一定不用更改，所以只需从 \(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;
}
首发：2022-04-20 09:12:42
标签：cnt,include,更改,int,题解,CF1635B From： https://www.cnblogs.com/liangbowen/p/16622840.html