题目描述

给定一个长度为 $n$ 的整数数组 $a$，我们希望将其变为单调不降（即对于所有 $1 \le i < n$，有 $a_i \le a_{i+1}$）。
可以执行的操作为：

• 选择两个不同下标 $i, j$（$1 \le i, j \le n, i \neq j$），将 $a_i$ 和 $a_j$ 合并为一个新数字（值为 $a_i + a_j$），并从数组中删除原来的 $a_i$ 和 $a_j$；
• 数组现在只剩下 $n - 2$ 个数字，保留其原有顺序并将新数字插入到数组的任意位置（可以在开头、末尾，也可以在任意两个元素之间）；
• 如此操作可以反复执行。

问：最少需要执行多少次上述操作，才能使得数组单调不降？

思路与方法

1. 问题转化

在每次合并操作中，“拿走”了两个原数组中的元素，将它们替换为一个新数字，数组长度因此减少 1。倘若我们并不关心新数字插入在哪个位置具体是多少值，而只关心最终能否让数组变成单调不降，那么可以把该操作视为：

• 一次操作“可以去掉两个我们不想保留的原数组元素”。

因此，假如我们知道在原数组中最少需要删除多少个元素才能使剩下的元素单调不降，则每次合并能够同时“去掉”其中的两个不想要的元素。也就是说，要删除 $\Delta$ 个元素，只需执行 $\lceil \tfrac{\Delta}{2} \rceil$ 次合并即可。

2. 如何求最少删除多少元素

我们把问题“最少删除多少元素，使原数组剩下的子序列单调不降”转化为“最大保留多少元素，可以组成一个单调不降子序列”。这即是 最长非降子序列(LNDS,Longest Non-Decreasing Subsequence)的问题。

• 令该最长非降子序列的长度为 $L$。
• 那么最少需要删除的元素数即为 $\Delta = n - L$。

3. 合并操作次数

在确定需要删除的元素数 $\Delta$ 后，每次合并可去掉其中的 2 个，则合并次数为： $\left\lceil \frac{\Delta}{2} \right\rceil =$ $\left\lceil \frac{n - L}{2} \right\rceil$ 在编程实现时常写为 $\bigl(n - L + 1\bigr)//2$（对于正整数计算，此公式与上面等价）。

4. LNDS 的求法

与经典的“最长非降（或严格上升）子序列”算法类似，可使用二分（Patience Sorting）方法：

• 依次遍历数组，对每个元素在“尾数组” tail 中用二分查找合适的替换/插入位置；
• 若当前元素 $x$ 不小于 tail 的最后一个元素，则直接追加到末尾；
• 否则用二分找到 tail 中第一个大于 $x$（对于非降，可以用 bisect_right）的位置，替换之。

这样 tail 的长度始终保持为当前遍历下的LNDS长度；遍历结束后 tail 的长度就是 $L$。
时间复杂度为 $O(n \log n)$。

5. 复杂度分析

• 对每个测试用例，我们使用 $O(n \log n)$ 时间求出 LNDS 长度，然后再做一次简单计算即可。
• 本题的限制（多个测试数据，且 $\sum n$ 不超过 $2 \times 10^5$），该方法足以在合理时间内运行完成。

代码实现

Python 代码

import sys
import bisect

input_data = sys.stdin.read().strip().split()
T = int(input_data[0])
idx = 1

results = []
for _ in range(T):
    # 读取数组长度
    n = int(input_data[idx])
    idx += 1
    # 读取数组
    arr = list(map(int, input_data[idx:idx + n]))
    idx += n
    
    # tail用于维护当前的“最长非降子序列”的尾部元素
    tail = []
    for x in arr:
        # 寻找 x 在 tail 中可以插入的位置(非降 -> 使用bisect_right)
        pos = bisect.bisect_right(tail, x)
        if pos == len(tail):
            # 如果pos在末尾，则追加
            tail.append(x)
        else:
            # 否则替换
            tail[pos] = x
    
    # LNDS长度
    L = len(tail)
    # 需要删除的元素个数
    to_delete = n - L
    # 每次合并能去掉2个元素，故操作次数=ceil(to_delete/2)
    ans = (to_delete + 1) // 2
    results.append(str(ans))

print("\n".join(results))

Java 代码

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 测试数据组数
        
        // 用StringBuilder拼接结果输出，避免频繁IO
        StringBuilder sb = new StringBuilder();
        
        while (T-- > 0) {
            int n = sc.nextInt(); // 数组长度
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            
            // 用ArrayList维护tail
            // tail的大小即为LNDS的长度
            ArrayList<Integer> tail = new ArrayList<>();
            
            for (int x : arr) {
                // 在tail中寻找第一个大于x的位置，若没找到则在末尾追加
                // 注意：对于非降序，需要用“大于x”来替换，对应bisect_right的思路
                int pos = binarySearchRight(tail, x);
                if (pos == tail.size()) {
                    tail.add(x);
                } else {
                    tail.set(pos, x);
                }
            }
            
            int L = tail.size();       // LNDS长度
            int toDelete = n - L;      // 需要删除的数量
            int ans = (toDelete + 1) / 2; // 合并次数
            
            sb.append(ans).append("\n");
        }
        
        System.out.print(sb);
    }
    
    // 找到tail中第一个大于x的下标(用于非降序的bisect_right)
    // 如果所有元素都<=x，则返回tail.size()
    private static int binarySearchRight(ArrayList<Integer> tail, int x) {
        int left = 0, right = tail.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tail.get(mid) <= x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left; 
    }
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

/*
 * 思路：
 * 1. 先求数组的最长非降子序列(LNDS)长度 L
 * 2. 需要删除 n - L 个元素，使剩余部分单调不降
 * 3. 因为一次合并可以“去掉”2个待删除元素，故最终操作次数=ceil((n - L)/2)
 */

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<long long> arr(n);
        for(int i = 0; i < n; i++){
            cin >> arr[i];
        }
        
        // tail用于维护LNDS
        vector<long long> tail;
        tail.reserve(n); // 预留空间
        
        for(auto &x : arr){
            // 在tail中寻找第一个大于x的位置(非降->bisect_right)
            // 若未找到则push_back
            auto pos = upper_bound(tail.begin(), tail.end(), x);
            if(pos == tail.end()){
                tail.push_back(x);
            } else {
                *pos = x;
            }
        }
        
        // LNDS长度
        int L = (int)tail.size();
        // 需要删除的数量
        int toDelete = n - L;
        // 操作次数
        int ans = (toDelete + 1) / 2;
        
        cout << ans << "\n";
    }
    
    return 0;
}

题目内容

小笨有一个长度为 $n$ 的数组 $a$，但众所周知小笨只对单调不降的数组感兴趣，即：$a_i≤a_i+1(1≤i≤n)$

现在，小苯希望将 $a$ 变成他感兴趣的数组，为此他可以做以下操作：

• 选择两个不同的下标 $i, j (1 ≤ i, j ≤ n, i ≠ j)$，将 $a_i$ 和 $a_j$ 合并成一个新数字，值为 $a_i + a_j$ ，并将 $a_i$ 和 $a_j$ 分别删除，剩余的 $n - 2$ 个数字按照原顺序拼接起来，接着将 $a_i$ + $a_j$ 这个新数字插入数组的任意位置。（可以是任意两个元素中间，也可以是 $a_1$ 的前面，也可以是 $a_n$ 的后面。）

小苯想知道，他至少需要执行多少次操作，才能使得 $a$ 数组单调不降，请你帮他算一算吧。

输入描述

本题有多组测试数据。

输入的第一行包含一个正整数 $T (1 ≤ T ≤ 100)$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行输入一个正整数$n(1≤n≤10^5)$,表示数组 $a$ 的长度。

第二行输入$n$个正整数,表示数组$a$,其中$1≤a_i≤10^9$

（保证所有测试数据中，$n$ 的总和不超过 $2 × 10^5$ 。）

输出描述

对于每组测试数据：

在单独的一行输出一行一个整数，表示至少要执行的操作次数。

样例1

输入

2
5
1 3 2 2 1
4
1 2 3 4

输出

1
0