codeforces Hello 2024 - C - Grouping Increases --- 题解

目录

Grouping Increases

题目描述：

思路解析：

代码实现：

---

Grouping Increases

题目描述：

        给你一个大小为n的数组a，你可以把数组a划分为两个子序列s和t，a中元素，要么在子序列s中，要么在子序列t中，对于大小为 m的数组 b ，定义数组 b 的惩罚 p(b)为 1 和 m−1 之间索引 i 的个数，其中 bi<bi+1。子序列要求元素的索引位置和之前的数组索引位置，保持相对一致。p（a）=p（s）+p（t），要求惩罚最小，并输出这个最小值。

思路解析：

        错误思路：当时我想的是，可以用至少几个序列可以将这个数组划分为全为递减序的序列，就这些序列接在一起，变成两个序列，这个序列数-2就是最小惩罚值，对某些案例确实是正确的，但是他有可能在接在一起后，会改变序列的性质，导致变为非序列。所以这个思路是不可行的。

        正确思路：用两个序列来接a[i]这个数字，优先接在第一个序列上，不行就接在第二个序列上，如果都不行，就接在第一个序列上，此时惩罚数+1；但是有一个问题是优先接在第一个序列上，所以如果序列1的末尾位置和序列2的末尾位置都能接上这个数字，并且序列1的末尾数字>序列2的末尾数字，那么优先接在序列1不是最优的，所以当序列1的末尾数字>序列2的末尾数字时就需要交换序列1和序列2的末尾数字。

代码实现：

import java.io.IOException;
import java.util.*;/*** @ProjectName: study3* @FileName: G* @author:HWJ* @Data: 2023/6/16 8:13*/
public class Main {public static void main(String[] args) throws IOException {Scanner input = new Scanner(System.in);int t = input.nextInt();for (int o = 0; o < t; o++) {int n = input.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = input.nextInt();}int t1 = Integer.MAX_VALUE;int t2 = Integer.MAX_VALUE;int res = 0;for (int i = 0; i < n; i++) {if (t1 > t2){int tmp = t1;t1 = t2;t2 = tmp;}if (t1 >= arr[i]){t1 = arr[i];} else if (t2 >= arr[i]) {t2 = arr[i];}else {t1 = arr[i];res++;}}System.out.println(res);}}}