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