题目链接

小红的好数组

题目描述

小红定义一个数组为好数组当且仅当这个数组至少存在一个长度为3的非降序子数组。小红可以进行多次操作，每次操作可以修改数组中的一个元素。小红想知道至少需要操作几次才可以把这个数组变成不是好数组。

输入:

  • 第一行输入一个整数 ，表示数组的长度
  • 第二行输入 个整数 ，表示数组的初始值

输出:

  • 一个整数，表示最少需要的操作次数

解题思路

这是一个贪心问题，可以通过以下步骤解决：

  1. 关键发现：

    • 要使数组不是好数组，就要破坏所有长度为3的非降序子数组
    • 对于连续的三个数 a[i-1], a[i], a[i+1]：
      • 如果 a[i] >= a[i-1] 且 a[i] <= a[i+1]，这就是一个非降序子数组
      • 我们必须修改中间的数 a[i] 来破坏这个非降序关系
    • 修改完一个位置后，可以跳过下一个位置（因为已经破坏了包含它的所有长度为3的非降序子数组）

  2. 贪心策略：

    • 从左到右遍历数组
    • 当找到一个非降序的三元组时：
      • 修改中间的数
      • 跳过下一个位置（因为已经不可能形成非降序子数组）
    • 统计需要修改的次数

  3. 具体步骤：

    • 遍历数组中的每个位置 i（从1到n-2）
    • 检查 a[i-1], a[i], a[i+1] 是否构成非降序
    • 如果是，则需要修改 a[i]，并跳过 i+1

代码

#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int &x : a) {
        std::cin >> x;
    }

    std::vector<int> b(n);
    int ans = 0;
    for (int i = 1; i < n - 1; i++) {
        if (a[i] >= a[i - 1] && a[i] <= a[i + 1]) {
            ans++;
            i += 1;  // 跳过下一个位置
        }
    }

    std::cout << ans << "\n";
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        int ans = 0;
        for(int i = 1; i < n - 1; i++) {
            if(a[i] >= a[i - 1] && a[i] <= a[i + 1]) {
                ans++;
                i++;  // 跳过下一个位置
            }
        }
        
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

ans = 0
i = 1
while i < n - 1:
    if a[i] >= a[i - 1] and a[i] <= a[i + 1]:
        ans += 1
        i += 2  # 跳过下一个位置
    else:
        i += 1

print(ans)

算法及复杂度

  • 算法：贪心
  • 时间复杂度： - 只需要遍历一次数组
  • 空间复杂度： - 需要存储输入数组