Codeforces Round #713 (Div. 3) E（思维）
Codeforces Round #713 (Div. 3) E（思维）
Here_SDUT
发布于 2022-08-08 17:40:22
发布于 2022-08-08 17:40:22
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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-4-14 1，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录