小红的好数组

[题目链接](https://www.nowcoder.com/practice/b8c3a24867c246f7a04da28e5da646ee)

思路

问题转化

"好数组"定义为存在至少一个长度为 3 的非降序连续子数组，即存在某个 使得 。我们需要通过最少的修改次数，使数组中不存在任何这样的三元组。

定义相邻对的关系：（ 或 ）。那么出现"坏三元组"等价于存在连续两个 。因此目标是：修改最少的元素，使得 数组中没有连续的两个 。

关键观察：修改一个元素的效果

修改 时，可以自由选择新值，从而控制 （ 与 的关系）和 （ 与 的关系）。但在一段非降序区间内，由于 ，无法同时让 且 。也就是说，一次修改只能将 或 中的一个翻转为 。

分段贪心

不同的非降序连续段之间互不影响（被下降对隔开）。对于一段长度为 的极长非降序子数组（ 个元素、 个连续的 ），需要在其中插入足够多的"断点"使得不存在连续两个 。

个连续的 ，每次修改消除其中一个 ，最少需要 次修改。

例如：

  • （一对非降序）： 次，本身不构成三元组。
  • （）： 次，修改中间元素即可。
  • （）： 次，修改第 2 个元素，变为 。
  • （）： 次。

算法

  1. 从左到右扫描数组，找出每一段极长非降序子数组的长度 。
  2. 对每段累加 。
  3. 输出总和。

样例演示

数组 的非降序段为：、、。

  • 段 长度 ，贡献 。
  • 其余段长度 ，贡献 。

答案为 。

复杂度

  • 时间复杂度：，单次遍历。
  • 空间复杂度：，存储数组（可优化为 边读边算）。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    int ans=0;
    int i=0;
    while(i<n){
        int j=i;
        while(j+1<n && a[j]<=a[j+1]) j++;
        int len=j-i+1;
        ans+=(len-1)/2;
        i=j+1;
    }
    printf("%d\n",ans);
    return 0;
}

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
        int ans = 0;
        int i = 0;
        while (i < n) {
            int j = i;
            while (j + 1 < n && a[j] <= a[j + 1]) j++;
            int len = j - i + 1;
            ans += (len - 1) / 2;
            i = j + 1;
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = 0
i = 0
while i < n:
    j = i
    while j + 1 < n and a[j] <= a[j + 1]:
        j += 1
    length = j - i + 1
    ans += (length - 1) // 2
    i = j + 1
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    let ans = 0;
    let i = 0;
    while (i < n) {
        let j = i;
        while (j + 1 < n && a[j] <= a[j + 1]) j++;
        const len = j - i + 1;
        ans += Math.floor((len - 1) / 2);
        i = j + 1;
    }
    console.log(ans);
});