小苯的数组操作

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

题目理解

给定长度为 的数组 ，允许以下两种操作（至多 次）将数组变为严格递减：

1. 操作1（加法）：选择前缀 和整数 ，令 （）。
2. 操作2（取模）：选择前缀 和整数 ，令 （）。

要求构造合法方案。

思路

关键观察

加法操作的核心性质：对前缀 的所有元素加同一个值 ，不改变该前缀内元素间的相对差。也就是说，（）保持不变。

这意味着：如果处理位置 时对前缀 加某个值，不会破坏已经满足的 的顺序关系（差值不变，若原来差为正，加后仍为正）。

构造方案（至多 次操作）

第一步（1次操作）：对整个前缀 执行操作2，令 。

此后所有元素都在 范围内。

第二步（至多 次操作）：从右到左处理，对 下降到 ：

• 若 ，对前缀 执行操作1，令 。

- 此时 变为 ，满足 。

- 由于加法不改变前缀内的差值，之前已经满足的相对顺序 保持不变。

• 若 ，跳过。

总操作次数：，满足限制。

样例演示

输入 ，：

1. 对前缀 取模 （）：
2. ：，跳过
3. ：，跳过
4. ：，对前缀 加 ：
5. ：，对前缀 加 ： ✓

共 3 次操作，，合法。

复杂度

• 时间复杂度：（每次加法操作需更新前缀，最坏 次操作各 更新）
• 空间复杂度：

代码

C++

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<long long> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    if (n == 1) {
        cout << 0 << "\n";
        return 0;
    }

    vector<tuple<int,int,long long>> ops;

    // 步骤1：对全前缀取模 n+1，使所有值落入 [0, n]
    long long mod_val = (long long)n + 1;
    ops.push_back({2, n, mod_val});
    for (int i = 1; i <= n; i++) a[i] %= mod_val;

    // 步骤2：从右到左，若不满足严格递减则对前缀加差值+1
    for (int i = n-1; i >= 1; i--) {
        if (a[i] <= a[i+1]) {
            long long add_val = a[i+1] - a[i] + 1;
            ops.push_back({1, i, add_val});
            for (int j = 1; j <= i; j++) a[j] += add_val;
        }
    }

    cout << ops.size() << "\n";
    for (auto& [t, p, x] : ops) {
        cout << t << " " << p << " " << x << "\n";
    }

    return 0;
}

Java

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

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().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        if (n == 1) {
            System.out.println(0);
            return;
        }

        List<long[]> ops = new ArrayList<>();

        long modVal = (long) n + 1;
        ops.add(new long[]{2, n, modVal});
        for (int i = 1; i <= n; i++) a[i] %= modVal;

        for (int i = n - 1; i >= 1; i--) {
            if (a[i] <= a[i + 1]) {
                long addVal = a[i + 1] - a[i] + 1;
                ops.add(new long[]{1, i, addVal});
                for (int j = 1; j <= i; j++) a[j] += addVal;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(ops.size()).append('\n');
        for (long[] op : ops) {
            sb.append(op[0]).append(' ').append(op[1]).append(' ').append(op[2]).append('\n');
        }
        System.out.print(sb);
    }
}