自动搬运

查看原文

来自洛谷，原作者为

	是青白呀 咕咕咕？咕咕咕！

搬运于2025-08-24 22:44:15，当前版本为作者最后更新于2023-02-01 19:18:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8976 「DTOI-4」排列

update 2023/2/2 添加了一个例子便于理解

题目描述

给你一个偶数 $n$ 和两个整数 $a, b$，请你构造一个长为 $n$ 的排列 $p$，使得其满足 $\displaystyle\sum_{i = 1}^{\frac{n}{2}} p_i \geq a$ 且 $\displaystyle\sum_{i = \frac{n}{2} + 1}^{n} p_i \geq b$。无解则输出 $-1$。

思路分析

要将长度为 $n$ 的排列分为两部分，分别满足两个不小于某个值的条件，则在考虑其中一个条件时，一定要尽可能使另一个条件能被得到满足。

在本题中，在考虑区间 $\left[1,\frac{n}{2} \right]$ 时，要使该区间和等于 $a$，才能使后半部分区间和大于等于 $b$ 的条件尽可能被满足。于是考虑如何选取 $\frac{n}{2}$ 个数使得其和为 $a$。首先我们容易知道，可以使得和为 $a$ 的条件为 $a \in \left[\frac{n(1+\frac{n}{2})}{4},\frac{n(\frac{n+1}{2}+n)}{4} \right]$，其中左右边界分别对应取 $\left[1,\frac{n}{2} \right]$ 的所有数和取 $\left[\frac{n+1}{2},n \right]$ 的所有数的情况。考虑先选 $\left[1,\frac{n}{2} \right]$ ，此时 $sum=\frac{n(1+\frac{n}{2})}{4}$。考虑将已选择的数替换为更大的数。为了避免替换时发生重复，每一次将已选中的 $\left[1,\frac{n}{2} \right]$ 中最大的数 $maxn$ 替换为 $maxn+\frac{n}{2}$，则每替换一次，$sum$ 的值增加 $\frac{n}{2}$。则我们共需操作 $\lfloor \frac{a-sum}{\frac{n}{2}} \rfloor$ 次，并将下一个 $maxn$ 替换为 $maxn+(a-sum) \mod \frac{n}{2}$ 的值。这样可以保证所选择的数不重复。最后再判断剩余数的和是否满足大于等于 $b$ 即可。

为了便于理解，这里举一个例子。

1
8 23 13

一开始我们选中的是这些数：

1 2 3 4

此时 $sum=10$，太小了，与目标 $a=23$ 的差值为 $13$。接下来进行上述替换操作。

1 2 3 8
1 2 7 8
1 6 7 8

此时的 $sum$ 为 $22$。到此，我们共操作了 $\lfloor \frac{a-sum}{\frac{n}{2}} \rfloor$ 次，即 $3$ 次，每一次都让 $sum$ 的值增加了 $4$。若再操作一次使 $1$ 变成 $5$，$sum$ 的值就会超过 $a$，不满足我们的贪心策略，进而使后四个数不小于 $b$ 的要求无法满足。所以我们将最后一个 $maxn$ 替换为 $maxn+(a-sum) \mod \frac{n}{2}$，使得 $sum=a$。代入数据发现，在这里我们应将 $1$ 替换为 $2$。则最后的序列为：

2 6 7 8 1 3 4 5

恰好满足条件。

这里需要注意，$a<\frac{n(1+\frac{n}{2})}{4}$ 不意味着无解，在这种情况下直接判断 $b$ 与 $\frac{n(\frac{n+1}{2}+n)}{4}$ 的关系即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int t;
signed main(){
	int t;
	read(t);
	while(t--){
		int n,a,b;
		read(n),read(a),read(b);
		int sum=(1+n/2)*n/4;
		if(sum>=a){//a选择1~n/2
			if((1+n)*n/2-sum<b)printf("-1\n");
			else{
				for(int i=1;i<=n;i++)
				    printf("%d ",i);
				printf("\n");
			}
			continue;
		}
		int movnum=(a-sum)/(n/2);//增加n/2的次数
		if(movnum>n/2||(movnum==n/2&&(a-sum)%(n/2))){//总操作次数不能大于n/2
			printf("-1\n");
			continue;
		}
		bool vis[N]={};//标记哪些数属于前半部分
		int suma=0;
		for(int i=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(int i=(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(int i=1;i<=n;i++)
		    	if(vis[i])printf("%d ",i);
		    for(int i=1;i<=n;i++)
		    	if(!vis[i])printf("%d ",i);
		    printf("\n");
		}
	}
	return 0;
}