本文涉及知识点

构造

P8976 「DTOI-4」排列

题目背景

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

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

---

构造一个排列 $p$，使得$下标为奇数的项之和\ge a且下标为偶数的项之和\ge b。$

题目描述

小 L 给你一个偶数 $n$ 和两个整数 $a,b$，请你构造一个长为 $n$ 的排列 $p$，使得其满足 $\sum _{i=1}^{\frac{n}{2}}{p}_i\ge a$ 且 $\sum _{i=\frac{n}{2}+1}^n{p}_i\ge b$。

输入格式

本题有多组测试数据。

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

对于每组数据：

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

输出格式

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

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

输入输出样例 #1

输入 #1

2
6 6 12
6 8 14

输出 #1

1 6 2 5 3 4
-1

说明/提示

本题开启 Special Judge。

$\text{Subtask}$	$n$	$a,b$	分值
$1$	$2\le n\le 10$	无特殊限制	$20\mathrm{pts}$
$2$	无特殊限制	$a=b=0$	$10\mathrm{pts}$
$3$	同上	$a=0$ 或 $b=0$	$10\mathrm{pts}$
$4$	同上	无特殊限制	$60\mathrm{pts}$

对于 $100\%$ 的数据，$2\le n,\sum n\le 10^5$，$0\le a,b\le \frac{n(n+1)}{2}$，$1\le T\le 10$，$n$ 为偶数。

构造

const long long M = N / 2;
long long x1 = (1 + M) * M / 2; 
long long x2 = (M + 1 + 2 * M) * M / 2;

x1是最小的一半数之和，x2是最大的一半数之和。
如果a>x2，无解。
x = max(x1,a) 余下的都给b，如果不足，则无解。
令$y=x-x1$故y$\in [0,x2-x1],x2-x1=2\times M\times M/2=M\times M$。
(i,i+M)共M组，如果$M|y$，则任选$\frac{y}{M}$组。
c1 = y/M,c2=y%M。
如果$c1\le M-2$
M和M+c2换，其它c1组从其它M-2组（除1组和c2组外)中选。
如果$c1>M-2$
全部换了在换回来。
$M+1\sim 2\times M$ 换M，减少$1\sim M-1$
$M+1\sim 2\times M$ 换1，减少$M\sim 2M-1$
结合一起就是$1\sim 2M-1$

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>#include <bitset>
using namespace std;template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {vector<T> ret;T d ;while (n--) {scanf(pFormat, &d);ret.emplace_back(d);}return ret;
}template<class T = int>
vector<T> Read( const char* pFormat = "%d") {int n;scanf("%d", &n);vector<T> ret;T d;while (n--) {scanf(pFormat, &d);ret.emplace_back(d);}return ret;
}class Solution {public:vector<int> Ans(int N,long long a,long long b ) {const long long M = N / 2;long long x1 = (1 + M) * M / 2;long long x2 = (M + 1 + 2 * M) * M / 2;if (a > x2) { return { -1 }; }long long x = max(x1, a);if(x1+x2-x < b ) { return { -1 }; }long long x3 = (x - x1) / M;long long x4 = (x - x1) % M;if (x3 >= M-1 ) {vector<int> ans(N);iota(ans.begin(), ans.begin() + M, M + 1);iota(ans.begin() + M, ans.end(), 1);if (M - 1 == x3) {const int i1 = (M+1)-(M - x4) - 1 + M;swap(ans[i1], ans[0]);}return ans;}vector<int> ans1, ans2;vector<bool> has(M + 1);int iInit = 0;if (0 != x4){ans1.emplace_back(1);ans1.emplace_back(M + 1);ans2.emplace_back(M + 1 - x4);ans2.emplace_back(M * 2 + 1 - x4);has[1] = has[M + 1 - x4] = true;iInit += 2;}for (int i = 1; i <= M; i++) {if (has[i]) { continue; }if (ans1.size() < x3 + iInit) {ans1.emplace_back(i + M);ans2.emplace_back(i);}else {ans1.emplace_back(i );ans2.emplace_back(i + M);}}ans1.insert(ans1.end(), ans2.begin(), ans2.end());return ans1;}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGint T;scanf("%d", &T);while (T--) {int n;long long a,b;cin >> n >> a >> b;Solution slu;auto res = slu.Ans(n, a, b);for (auto i : res){std::cout << i << " ";}std::cout << std::endl;}return 0;
}

单元测试

		void Check(vector<int>& res,int N,long long a,long long b) {set<int> s(res.begin(),res.end());bool b2 = s.size() == N;Assert::IsTrue(b2);Assert::AreEqual(1, *s.begin());Assert::AreEqual(N, *s.rbegin());const int M = N / 2;const auto a1 = accumulate(res.begin(), res.begin() + M, 0LL);const auto b1 = accumulate(res.begin() + M, res.end(), 0LL);Assert::IsTrue(a1 >= a);Assert::IsTrue(b1 >= b);}TEST_METHOD(TestMethod11){		auto res = Solution().Ans(6, 16, 1);AssertEx(vector<int>{-1}, res);}TEST_METHOD(TestMethod12){auto res = Solution().Ans(6 ,1, 16);AssertEx(vector<int>{-1}, res);}TEST_METHOD(TestMethod13){Test(4);}TEST_METHOD(TestMethod14){Test(6);}TEST_METHOD(TestMethod15){Test(8);}TEST_METHOD(TestMethod16){Test(10);}TEST_METHOD(TestMethod17){Test(12);}TEST_METHOD(TestMethod18){Test(14);}TEST_METHOD(TestMethod19){Test(100);}void Test(int N) {const long long M = N / 2;long long x1 = (1 + M) * M / 2;long long x2 = (M + 1 + 2 * M) * M / 2;for (long long a = x1-1; a <= x2; a++) {auto res = Solution().Ans(N, a, 1);Check(res, N, a, 1);}}		

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。