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

E. Permutation by Sum

题目链接

题意:

给你一个排列(1到n每个数字都出现且只出现一次),要求你用排列中的数字构造一个新数组,使得下标为lr的数字之和等于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;
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇