Codeforces Round #713 (Div. 3) E（思维）

Here_SDUT

发布于 2022-08-08 17:40:22

1800

发布于 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 删除

permutation