牛客周赛--round 80--F题--构造+贪心（应该算是贪心吧）
链接：https://ac.nowcoder.com/acm/contest/101196/F
来源：牛客网

题目描述

集训队有 2×n 名队员备战鹿瓜杯比赛。已知第 i 名队员的实力为 i ，现在需要准备 n 场训练赛，将实力相近的队员匹配到一起进行训练。
每场训练赛为两人进行对局，每个队员都需要参加且仅参加一场训练赛。每一场训练赛的不和谐度为参赛双方的实力之差的绝对值。请你判断，在所有训练赛的组合方式中，是否存在不和谐度之和恰好为 k 的情况。如果有，输出任意一种组合方式。

输入描述: 

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦10^5) 代表数据组数，每组测试数据描述如下：在一行上输入两个正整数 n,k(1≦n≦10^6; 1≦k≦10^12)代表需要准备的训练赛的场次数量，以及最终不和谐度的总和。除此之外，保证单个测试文件的 n 之和不超过 10^6。

输出描述: 

对于每一组测试数据，如果不存在不和谐度之和恰好为 k 的组合方式，直接输出 −1；否则，输出 n 行，每行输出两个不同的正整数 i,j(1≦i,j≦2×n)，代表一场训练赛的参赛双方。

题型：

构造+贪心（应该算是贪心吧）

思路：

分类讨论
首先分析一下输出为-1的情况
1.取每一对的差值绝对值最小：由于每一个队员的实力不同，所以每一对的差值的绝对值最小为1，所以当k<n时，输出一定为-1
2.取每一对的差值绝对值最大：易得输入为n时，差值总和的绝对值最大为1+3+......+(2n-3)+(2n-1)=n^2，所以当k>n^2时，输出一定为-1
3.当n为奇数时，差值总和一定为奇数；n为偶数时，差值总和一定为偶数；所以当k%2!=n%2时，输出一定为-1
（注：要证明第3点其实很简单，我们发现，每一对的差值的绝对值一定为奇数，那么，n为偶数时，其差值的绝对值之和为偶数个奇数相加，其结果必定是偶数；奇数同理）
输出为-1的情况为以上3种，下面讨论输出不为-1的情况
可以采取“能贪则贪的策略”
举个例子，对于n=3,k=9，其安排的方式很多，有3,3,3;5,3,1;4,4,1；但是对于n=3,k=7,其方式只有一种：5,1,1(3,3,1应该是不行的)；此时注意到，对于每一个k，似乎都可以先尝试获取最大差值的绝对值，再尝试获取小一些的值
如何尝试获取最大差值的绝对值呢？我们设目前剩余未被安排的数（选手）里面的最大值为r,最小值为l，那么最大差值的绝对值是（r-l）,当减去这个最大差值的绝对值，剩下的值为k-(r-l)
此时，如果k-(r-l)这个值小于之后还需要安排的对数，那么就表示不能够贪最大值，只能够获取相邻的两个数（这里贪次大值没有必要，因为如果次大值能够贪，那么下一对组合一定为次大值）
如果k-(r-l)这个值大于等于之后还需要安排的对数，那么就表示能够贪最大值，此时获取l,r并输出即可

注意点

1.看数据范围，记得开long long
2.不要漏掉l,r,n,k四个变量的增减操作

代码： 

#include<bits/stdc++.h>
#define int long long int
using namespace std;
signed main() {
	int T;
	scanf("%lld",&T);
	while(T--) {
		int n,k;
		scanf("%lld%lld",&n,&k);
		if(k<n || k>n*n || k%2!=n%2) { //输出为-1的情况
			printf("-1\n");
			continue;
		}
		int l=1,r=2*n;
		while(l<r) {
			if(k-(r-l)>=(n-1)) { //能贪就贪，贪不了就取相邻的两个
				printf("%lld %lld\n",l,r);
				k-=(r-l);
				l++;
				r--;
				n--;
			}else{
				printf("%lld %lld\n",l,l+1);
				k-=1;
				l+=2;
				n--;
			}
		}
	}
	return 0;
}
(P.S.:话说牛客题解的标签选择里面怎么没有“构造”这个标签...)