P8976 「DTOI-4」排列，贪心

题目背景

Update on 2023.2.1：新增一组针对 @yuanjiabao 的 Hack 数据，放置于 #21。

Update on 2023.2.2：新增一组针对 @CourtesyWei 和 @bizhidaojiaosha 的 Hack 数据，放置于 #22。

题目描述

小 L 给你一个偶数 n 和两个整数a,b，请你构造一个长为 n 的排列 p，使得其满足 ∑2n​​pi​≥a 且2n​+1∑n​pi​≥b。

输入格式

本题有多组测试数据。

第一行，一个整数 T，表示数据组数。

对于每组数据：

一行，三个整数 n,a,b。

输出格式

对于每组数据，如果无解，输出 -1；否则，输出一行，n 个整数，表示你构造出的排列 p。

如有多解，输出任意一组均可。

输入输出样例

输入 #1复制

2
6 6 12
6 8 14

输出 #1复制

1 6 2 5 3 4
-1

说明/提示

本题开启 Special Judge。

SubtaskSubtask	n	a,b	分值
11	2≤n≤10	无特殊限制	⁡20pts
22	无特殊限制	a=b=0	⁡10pts
33	同上	a=0 或 b=0	10pts
44	同上	无特殊限制	60pts

对于 100%的数据，2≤n,∑n≤105，0≤a,b≤2n(n+1)​，1≤T≤10，n 为偶数。

解析 ：

首先，如果(n+1)*n/2>a+b,那么肯定没有正确答案，所以直接返回输出-1即可
否则，就有可能有可能有正确的答案；
我们可以先处理前n/2个，使其满足 suma>=a ，当然为了是 sumb>=b,我们要尽可能使 suma >=a,的情况下尽可能的小，这样才能使后面的sumb尽可能的大；
到这里，就已经有贪心的思路了：在满足要求的情况下尽可能的使答案最优，且满足二段性。
所以我们可以贪心 suma ，使suma在满足题意的情况下最优，然后判断剩下的数是否满足 sumb>=b, 

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
LL n, a, b;
LL arr[N], brr[N];int main() {int T;scanf("%d", &T);while (T--) {memset(brr, 0, sizeof brr);scanf("%lld%lld%lld", &n, &a, &b);if (a + b > n * (n + 1) / 2) {cout << -1 << endl;continue;}LL sum = 0;for (int i = 1; i <= n / 2; i++) {arr[i] = i;sum += i;}LL t = n;for (int i = n/2; i >0 && a > sum; i--) {LL c = a - sum;if (c <= t - arr[i]) {arr[i] += c;sum += c;t--;break;}else {sum += t - arr[i];arr[i] = t;t--;}}if ((1 + n) * n / 2 - sum < b || sum < a) {cout << -1 << endl;continue;}for (int i = 1; i <= n / 2; i++) {brr[arr[i]] = 1;}for (int i = 1, j = n / 2 + 1; i <= n; i++) {if (brr[i] == 0)arr[j++] = i;}for (int i = 1; i < n; i++) {printf("%lld ", arr[i]);}printf("%lld\n", arr[n]);}return 0;
}