大学 生免费商业网站设计,做网站一定要后台嘛,做二手车的网站,wordpress百度熊掌题目背景
Update on 2023.2.1#xff1a;新增一组针对 yuanjiabao 的 Hack 数据#xff0c;放置于 #21。
Update on 2023.2.2#xff1a;新增一组针对 CourtesyWei 和 bizhidaojiaosha 的 Hack 数据#xff0c;放置于 #22。 题目描述
小 L 给你一个偶数 n 和两个整数a,b…题目背景
Update on 2023.2.1新增一组针对 yuanjiabao 的 Hack 数据放置于 #21。
Update on 2023.2.2新增一组针对 CourtesyWei 和 bizhidaojiaosha 的 Hack 数据放置于 #22。 题目描述
小 L 给你一个偶数 n 和两个整数a,b请你构造一个长为 n 的排列 p使得其满足 ∑2npi≥a 且2n1∑npi≥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。
SubtaskSubtaskna,b分值112≤n≤10无特殊限制20pts22无特殊限制ab010pts33同上a0 或 b010pts44同上无特殊限制60pts
对于 100%的数据2≤n,∑n≤1050≤a,b≤2n(n1)1≤T≤10n 为偶数。
解析 首先如果(n1)*n/2ab,那么肯定没有正确答案所以直接返回输出-1即可 否则就有可能有可能有正确的答案 我们可以先处理前n/2个使其满足 sumaa 当然为了是 sumbb,我们要尽可能使 suma a,的情况下尽可能的小这样才能使后面的sumb尽可能的大 到这里就已经有贪心的思路了在满足要求的情况下尽可能的使答案最优且满足二段性。 所以我们可以贪心 suma 使suma在满足题意的情况下最优然后判断剩下的数是否满足 sumbb,
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemapusing 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;
}
