打卡信奥刷题（3292）用C++实现信奥题 P8976 「DTOI-4」排列

P8976 「DTOI-4」排列

题目背景

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

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

构造一个排列p pp，使得下标为奇数的项之和 ≥ a 且下标为偶数的项之和 ≥ b 。 \small\color{white}{下标为奇数的项之和 \geq a 且下标为偶数的项之和 \geq b。}下标为奇数的项之和≥a且下标为偶数的项之和≥b。

题目描述

小 L 给你一个偶数n nn和两个整数a , b a, ba,b，请你构造一个长为n nn的排列p pp，使得其满足∑ i = 1 n 2 p i ≥ a \displaystyle\sum_{i = 1}^{\frac{n}{2}} p_i \geq ai=1∑2n​​pi​≥a且∑ i = n 2 + 1 n p i ≥ b \displaystyle\sum_{i = \frac{n}{2} + 1}^{n} p_i \geq bi=2n​+1∑n​pi​≥b。

输入格式

本题有多组测试数据。

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

对于每组数据：

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

输出格式

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

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

输入输出样例 #1

输入 #1

2 6 6 12 6 8 14

输出 #1

1 6 2 5 3 4 -1

说明/提示

本题开启 Special Judge。

对于100 % 100\%100%的数据，2 ≤ n , ∑ n ≤ 10 5 2 \leq n, \sum n \leq 10^52≤n,∑n≤105，0 ≤ a , b ≤ n ( n + 1 ) 2 0 \leq a, b \leq \frac{n(n + 1)}{2}0≤a,b≤2n(n+1)​，1 ≤ T ≤ 10 1 \leq T \leq 101≤T≤10，n nn为偶数。

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e5+5;intt;signedmain(){intt;cin>>t;while(t--){intn,a,b;cin>>n>>a>>b;intsum=(1+n/2)*n/4;if(sum>=a){//a选择1~n/2if((1+n)*n/2-sum<b)printf("-1\n");else{for(inti=1;i<=n;i++)printf("%d ",i);printf("\n");}continue;}intmovnum=(a-sum)/(n/2);//增加n/2的次数if(movnum>n/2||(movnum==n/2&&(a-sum)%(n/2))){//总操作次数不能大于n/2printf("-1\n");continue;}boolvis[N]={};//标记哪些数属于前半部分intsuma=0;for(inti=1;i<(n/2)-movnum;i++)suma+=i,vis[i]=1;suma+=(n/2)-movnum+(a-sum)%(n/2);vis[(n/2)-movnum+(a-sum)%(n/2)]=1;for(inti=(n/2)-movnum+1;i<=n/2;i++)suma+=i+n/2,vis[i+n/2]=1;if((1+n)*n/2-suma<b)printf("-1\n");else{for(inti=1;i<=n;i++)if(vis[i])printf("%d ",i);for(inti=1;i<=n;i++)if(!vis[i])printf("%d ",i);printf("\n");}}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容