解题思路与方法

问题建模

我们需要对一个长度为 $n$ 的高度序列 $h_1, h_2, \dots, h_n$ 进行最少次数的“调整”，使得调整后的高度序列严格单调递增且相邻差至少为 1（高度为整数）。每次调整可将某个位置的高度改为任意整数；未调整的位置保持原值。

若我们选择不调整的一组位置 $S=i_1<i_2<\cdots<i_k$，并将其它位置在这两个未调整点之间“插值”成整数严格递增序列，那么必须保证对于任意相邻的 $i_j,i_{j+1}\in S$，都有

即

令 $b_i = h_i - i$，则上述条件等价于在序列 $b_i$ 上选出一个最长非严格递增子序列（LNDS，longest non‑decreasing subsequence）。这样，能保留（不调整）的点数就是 LNDS 的长度 $L$，最少调整次数即为 $n - L$。

算法实现

1. 计算变换数组 $b_i = h_i - i$；
2. 在 $b$ 上求 LNDS 长度，可以用“耐心排序”技巧，维护一个数组 lis，对每个 $b_i$ 在 lis 上用二分查找找到第一个严格大于 $b_i$ 的位置并替换（对应非严格递增），若找不到则追加；
3. lis 的长度即为 LNDS，答案为 n - lis.size()。

该算法单组数据时间复杂度 $\mathcal O(n\log n)$，空间复杂度 $\mathcal O(n)$，能轻松应对 $n\le10^5$ 的规模，多组输入亦可。

代码实现

Python 代码

import sys
import bisect

def min_adjustments(h):
    """
    计算使 h 严格递增（相邻差 >=1）所需的最少位置调整次数
    """
    lis = []  # 存储 LNDS 的“牌堆顶”
    for idx, height in enumerate(h, start=1):
        delta = height - idx
        # bisect_right 用于非严格递增（<=）
        pos = bisect.bisect_right(lis, delta)
        if pos == len(lis):
            lis.append(delta)
        else:
            lis[pos] = delta
    return len(h) - len(lis)

def main():
    data = sys.stdin.read().strip().split()
    T = int(data[0])
    ptr = 1
    for _ in range(T):
        n = int(data[ptr]); ptr += 1
        h = list(map(int, data[ptr:ptr+n]))
        ptr += n
        print(min_adjustments(h))

if __name__ == "__main__":
    main()

Java 代码

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

public class Main {
    // 计算单组数据的最少调整次数
    private static int minAdjustments(int[] h) {
        ArrayList<Integer> lis = new ArrayList<>();
        for (int i = 0; i < h.length; i++) {
            int delta = h[i] - (i + 1);
            // 在 lis 中寻找第一个 > delta 的位置（upper_bound）
            int l = 0, r = lis.size();
            while (l < r) {
                int m = (l + r) / 2;
                if (lis.get(m) <= delta) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            if (l == lis.size()) {
                lis.add(delta);
            } else {
                lis.set(l, delta);
            }
        }
        return h.length - lis.size();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            String[] parts = br.readLine().split("\\s+");
            int[] h = new int[n];
            for (int i = 0; i < n; i++) {
                h[i] = Integer.parseInt(parts[i]);
            }
            System.out.println(minAdjustments(h));
        }
    }
}

C++ 代码

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

// 计算单组数据的最少调整次数
int minAdjustments(const vector<int>& h) {
    vector<long long> lis;
    for (int i = 0; i < (int)h.size(); i++) {
        long long delta = (long long)h[i] - (i + 1);
        // upper_bound 找到首个大于 delta 的位置，实现非严格递增
        auto it = upper_bound(lis.begin(), lis.end(), delta);
        if (it == lis.end()) {
            lis.push_back(delta);
        } else {
            *it = delta;
        }
    }
    return (int)h.size() - (int)lis.size();
}

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> h(n);
        for (int i = 0; i < n; i++) {
            cin >> h[i];
        }
        cout << minAdjustments(h) << "\n";
    }
    return 0;
}

题目内容

多多想要举办一场助农音乐节，音乐节将在收获果实的风景优美的山区举行，以提供独特的视听体验。然而，山区的自然地形往往起伏不平。为了确保观众的安全和良好的视听效果，场地的地形高度需要进行合理调整，确保每个位置的高度都要高于前一个位置，从而避免因地形起伏造成的摔倒或视线遮挡。在实际地形中，可能存在一些低洼区域需要填充，以及一些过高的区域需要切削。为了解决这一问题，多多希望通过尽量少的地形调整(即调整最少的测量点高度)，使整个场地的高度呈现严格上升的形态。请你帮多多计算，为了确保音乐节的成功举办，最少需要对多少个位置进行地形调整注意：数据范围仅限制输入值，调整后的数值可以超出范围。如调整后的高度可以为负数(允许变为谷底)

输入描述

第一行为一个整数 $T(1\leq T\leq 10)$, 表示共有 $T$ 个测试数据。

每组测试数据：

第一行为一个整数 $n(1\leq n\leq 100000)$，表示山区的测量点高度总数。

第二行有 $n$ 个整数 $h_i(1\leq h_i\leq 100000)$,表示每个测量点 $i$ 的地形高度。

输出描述

每组数据输出一个结果，每个结果占一行

补充说明

对于 $20$% 的数据有：$1\leq n\leq 1000$

对于 $100$% 的数据有：$1\leq n\leq 100000$

数据范围仅限制输入值，调整后的数值可以超出范围。如调整后的高度可以为负数(允许变为谷底)

示例1

输入

1
4
5 3 6 2

输出

2

说明

最少的地形调整次数为 $2$，可将下标为 $0$ 的 $5$ 调整为 $2$，下标为 $3$ 的 $2$ 调整为 $7$。

示例2

输入

1
3
1 2 3

输出

0

说明

最少的地形调整次数为 $0$，初始的高度已经满足要求。