模拟子序列的递增

描述

给出 $4$ 个数 $n,l,r,s$ ，求序列 $A = [1,2,..,n]$ 的一个排列，使得 $\sum_{i = l}^rA_i = s$ （下标从1开始），若无解则输出 $-1$ ，若存在多解，输出其中任意一个即可。
数据范围：

$1≤n≤500$
$1≤l≤r≤n$
$1≤s≤n(n+1)/2$

分析

对于这一题，我们可以这样理解，从序列 $A = [1,2,..,n]$ 中选取 $m = r-l+1$ 个数，使得它们的和等于 $s$ ，并把这 $m$ 个数按任意次序放到序列对应下标的 $l$ 至 $r$ 处，至于没有选到的数，按任意次序放到剩余位置即可。其实问题的关键就在于如何选取这 $m$ 个数，我们记这 $m$ 个数的集合为 $B$ ，元素之和记为 $sum(B)$ 。不难发现 $sum(B)∈[\frac{m(m+1)}{2}, \frac{m(n-m+1+n)}{2}]$ ，而且 $sum(B)$ 能取到这个闭区间内的任意一个整数，也就是说只要 $s$ 在这个范围内，那一定是有解的，反之无解。我们可以通过模拟直接证明这个结论，从左端点开始模拟 $sum(B)$ 的递增过程， $sum(B) = \frac{m(m+1)}{2}$ 时， $B = \{1, 2, ..., m \}$ ， $sum(B) = \frac{m(m+1)}{2} + k$ 时，我们将 $m$ 与后面的 $m+k$ 替换，得到 $B = \{ 1, 2, ..., m+k \}$ ，直至 $m+k = n$ 。当 $k > n - m$ 时，开始递增倒数第二个数，就这样一直到所有数都无法递增为止，即 $sum(B) = \frac{m(n-m+1+n)}{2}, B = \{ n-m+1, ..., n\}$ 。在模拟这个过程时不难发现，我们每次对当前数 $k$ 进行替换时恰好都可以在后面的序列中找到 $k+1$ ，因此可以得出上述结论。

解决

有了这个结论，问题的处理简单许多了，首先处理无解的情况，有解时，先求出 $s$ 与左端点的差，这就是递增的次数 $cnt = s - \frac{m(m+1)}{2}$ ，若 $cnt = 0$ 直接返回即可，否则需要进行增增操作。维护两个指针 $k_1, k_2$ ， $k_1$ 指向当前需要替换的元素（初始指向 $m$ ）， $k_2$ 指向后面的数组中最大的元素（初始指向数组末尾 $n$ ）。将 $A_{k_2} - A_{k_1}$ 与 $cnt$ 进行比较，若前者小于后者则说明将这一轮递增全部做完次数依然不够，将 $A_{k_1}$ 与 $A_{k_2}$ 进行替换， $cnt$ 更新为 $cnt - (A_{k_2} - A_{k_1})$ ，指针 $k_1$ 左移一位，而至于 $k_2$ ，注意到我们是将最大的元素，替换成了一个最小的元素，相当于是将一个循环数组（仔细观察其实还可以发现，它是递增连续的）原来的尾换成了新的头，所以我们也将 $k_2$ 左移一位即可，只不过当 $k_2$ 在移动前已经指向最左边的元素时（ $A_{m+1}$ ），将其移动至末尾，这样就可以保证 $k_2$ 始终指向后面数组中最大的元素了，更新完所有变量后，继续做下一轮比较。如果 $A_{k_2} - A_{k_1} ≥ cnt$ ，则说明这一轮可以将递增次数耗尽，递减 $k_2$ 直至 $A_{k_2} - A_{k_1} = cnt$ 随后交换 $A_{k_2} ,A_{k_1}$ 即可。这些操作做完后我们就可以保证 $\sum_{i = 1}^mA_i = s$ 了，随后将区间 $[1, m]$ 中的元素与 $[l,r]$ 的元素一一对应进行替换就即可，注意要从后向前进行替换，否则容易出问题。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t; cin >> t;
    int n, lp, rp, s;
    while(t--) {  // 一共有 t 个测试用例
        cin >> n >> lp >> rp >> s;
        int a[n];
        for(int i = 0; i < n; i++) a[i] = i+1;

        int len = rp-lp+1;
        if(s < len*(len+1)/2 || s > len*(n-len+1+n)/2) {  // 无解的情况
            cout << -1 << '\n';
            continue;
        }

        int sub = s - len*(len+1)/2;
        int k1 = len-1;
        int k2 = n-1;  // 始终指向后面数组中最大的元素

        if(sub) {
            while(sub > a[k2]-a[k1]) {
                sub -= (a[k2]-a[k1]);
                swap(a[k1--], a[k2]);
                if(k2 == len) k2 = n-1;
                else k2--;
            }

            while(sub < a[k2]-a[k1]) {
                if(k2 == len) k2 = n-1;
                else k2--;
            }
            swap(a[k1], a[k2]);
        }

        // 移动到[lp, rp]并打印
        k1 = len-1, k2 = rp-1;
        while(k1 >= 0) {
            swap(a[k1--], a[k2--]);
        }

        cout << a[0];
        for(int i = 1; i < n; i++) {
            cout << " " << a[i];
        }
        cout << '\n';
    }
}

总结

这是 $codeforces$ $div3$ 水平的题，题目本身不难，但是要把逻辑理清楚，并完整做出来对蒟蒻我来说也不算容易，尤其在代码编写的细节上，受语言所限，并不如伪代码所说的那么轻松，需要考虑很多细节。对于这种需要考验编码能力，逻辑思考能力而不是硬核算法的问题，我有种说不出来的喜欢，所以贴出来分享给大家。如果读者朋友有更好的解法和更简洁的代码，欢迎在评论区贴出来一起交流讨论。