牛客小白月赛68——F题

https://ac.nowcoder.com/acm/contest/51958/F

  非常折磨的一道题，需要注意许多细节问题（详见代码注释）。

  本题的关键性质是单次交换最多修正 $6$ 个点，所以两次交换最多只能存在 $12$ 个坏点，否则一定失败。每次处理一下坏点集合。且需要动态计算维护坏点集合，不同循环间的坏点集合是独立的。

#include <bits/stdc++.h>
using namespace std;

const int N = 310;
int a[N];
int n, k;

//注意每次需要动态统计，且在不同循环中坏点集合是独立的，所以需要以返回值返回，
//之前用的是全局变量，所以一直WA，哭死 
set<int> calc(){         //(i, j)对若存在问题，则i和j都是坏点（都可能通过交换使得这个对值修正） 
	//重新统计坏点情况
	set<int> pos; 
	for(int i = 1; i <= n; i++){
		if(i == 1 && abs(a[i] - a[n]) > k){
			pos.insert(i);
			pos.insert(n - 1);
		}
		else if(i > 1 && abs(a[i] - a[i - 1]) > k) {
			pos.insert(i);
			pos.insert(i - 1);
		}	
	}
	return pos;
}

void solve(){	
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	//筛选坏点 
	auto s = calc();
	if(s.size() == 0){
		puts("0");
		return;
	}
	if(s.size() > 12){   //超过了12说明2次交换一定无法修正 
		puts("-1");
		return;
	}
	else{	
		for(auto& i : s){   //单次操作最多修正6个坏点
			for(int j = 1; j <= n; j++){
				if(i == j) continue;
				swap(a[i], a[j]);
				auto s1 = calc();     
				if(s1.size() > 6) {
					swap(a[i], a[j]);
					continue;
				}
				for(auto& k : s1){
					for(int u = 1; u <= n; u++){
						if(k == u) continue;
						swap(a[k], a[u]);
						auto s2 = calc();
						if(s2.size() == 0){
							puts("2");
							printf("%d %d\n", i, j);
							printf("%d %d\n", k, u);
							return;
						}
						swap(a[k], a[u]);
					}
				}
				swap(a[i], a[j]);
			}
		}
		puts("-1");  	
	}
}

int main(){
	int T = 1;
	scanf("%d", &T);
	while(T -- ){
		solve();
	}
	return 0;
}