E. Permutation by Sum

题目链接

题意：

给你一个排列（1到n每个数字都出现且只出现一次），要求你用排列中的数字构造一个新数组，使得下标为l到r的数字之和等于s。

分析：

题目可以理解为，让你在1-n中挑k（r-l+1）个数字和为s。首先可以知道可以组成的数的理论最大值为 ${\displaystyle \sum _{i=n-k}^{n}i}$，理论最小值为${\displaystyle \sum _{i=1}^{k}i}$，并且处于这个范围之内的数都可以被正确的表示出来。故，只要s处于最小值和最大值之间就有解。

剩下就是如何找这k个数，定义两个函数：low(k)表示${\displaystyle \sum _{i=1}^{k}i}$,high(k,n) 表示${\displaystyle \sum _{i=n-k}^{n}i}$，即分别表示从1-n中取k个的最小值和最大值。我们令i = n，如果high(k, i) >= s && low(k - 1) <= s - i则表示i这个数字可以选取。其中式子的前半段表示，从1-i这些数中取k个数可以表达出s，后半段表示，如果选取i，那么在剩下的数中取k-1个数也可以表示出s-i，那么i这个数可以选用。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int sum[1111];
bool vis[1111];
int n, l, r, s, m;
int f;
int low(int k) { return sum[k]; }
int high(int k, int i) { return sum[i] - sum[i - k]; }
int ans[1111];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    for (int i = 1; i <= 510; i++) sum[i] = sum[i - 1] + i;
    while (t--) {
        cin >> n >> l >> r >> s;
        memset(vis, 0, sizeof vis);
        int k = r - l + 1, i = n;
        int now = l;
        while (k && i >= 1) {
            if (high(k, i) >= s && low(k - 1) <= s - i) {
                ans[now++] = i;
                vis[i] = 1;
                k--;
                s -= i;
            }
            i--;
        }
        if (s > 0)
            puts("-1");
        else {
            int now = 1;
            for (int i = 1; i <= n; i++) {
                if (l <= i && i <= r) continue;
                while (vis[now] == 1) now++;
                ans[i] = now++;
            }
            for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
            puts("");
        }
    }
    return 0;
}