模拟子序列的递增

描述

给出 个数 ，求序列的一个排列，使得（下标从1开始），若无解则输出 ，若存在多解，输出其中任意一个即可。
数据范围：

分析

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

解决

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

代码

#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';
    }
}

总结

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