Tokitsukaze and New RenKinKama

第一行包含一个整数 $T$ ( $1 \leq T \leq 300$ )~--- 测试数据的组数。

对于每组测试数据：

第一行包含两个整数 $n$ , $k$ ( $1 \leq n \leq 300$ , $0 \leq k \leq 10^9$ ) --- 素材的个数以及炼金釜的承受能力 $k$ 。

第二行包含一个长度为 $n$ 的序列 $v_1$ , $v_2$ , $\ldots$ , $v_n$ ( $0 \leq v_i \leq 10^9$ ) --- 每个素材的潜力值。要注意这些素材是按输入顺序围成一圈。

数据保证 $\sum n \leq 300$

对于每组测试数据：如果不能避免炼金釜爆炸，则输出 $-1$ 。

否则输出 $m+1$ 行：

第一行含一个整数 $m$ ( $0 \leq m \leq 2$ )，表示操作次数。

接下来 $m$ 行，每行输出选择的两个下标 $i$ , $j$ ( $1 \leq i,j \leq n$ ), 表示要交换当前的第 $i$ 个素材和第 $j$ 个素材。

如果有多种方案，输出任意一种即可。注意：不需要使操作次数最少。

C++(clang++ 11.0.1) 解法, 执行用时: 52ms, 内存消耗: 512K, 提交时间: 2023-03-12 10:40:05

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int a[N];
int n,k;

set<int> fun()
{
	set<int>s;
	for(int i=1;i<=n;i++)
	{
		if(i==1&&abs(a[i]-a[n])>k)
		{
			s.insert(1),s.insert(n);
		}
		else if(i!=1&&abs(a[i]-a[i-1])>k)
		{
			s.insert(i),s.insert(i-1);
		}
	}
	return s;
}

void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	auto x=fun();
	if(x.size()==0)
	{
		cout<<0<<endl;
		return;
	}
	else if(x.size()>12) 
	{
		cout<<-1<<endl;
		return;
	}
	for(int i:x)
	{
		for(int j=1;j<=n;j++)
		{
			swap(a[i],a[j]);
			auto y=fun();
			if(y.size()>6)
			{
				swap(a[i],a[j]);continue;
			}
			for(int l:y)
			{
				for(int r=1;r<=n;r++)
				{
					swap(a[l],a[r]);
					auto z=fun();
					if(z.size()==0)
					{
						cout<<2<<endl;
						cout<<i<<' '<<j<<endl;
						cout<<l<<' '<<r<<endl;
						return;
					}
					swap(a[l],a[r]);
				}
			}
			swap(a[i],a[j]);
		}
	}
	cout<<-1<<endl;
}

int main()
{
	std::ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 75ms, 内存消耗: 444K, 提交时间: 2023-04-16 09:12:17

#include<iostream>

using namespace std;
const int N=310;
int n,k;
int a[N];
pair<int,int> pii;

bool dfs(int cnt){
	if(cnt>2)	return false;
	int res[15]={0};
	int ti=0;
	for(int i=0;i<n;i++){
		if(abs(a[i]-a[(i-1+n)%n])>k||abs(a[i]-a[(i+1)%n])>k){
			res[ti++]=i;
		}
		if(ti>(2-cnt)*6)	return false;
	}

	if(ti==0){
		cout <<cnt <<endl;
		return true;
	}

	for(int i=0;i<ti;i++){
		int now=res[i];
		for(int j=0;j<n;j++){
			if(now!=j){
				swap(a[j],a[now]);
				if(dfs(cnt+1)){
					if(cnt==1)	pii.first=now+1,pii.second=j+1;		
					else cout <<now+1 <<" " <<j+1 <<endl;
					swap(a[j],a[now]);
					return true;
				}
				swap(a[j],a[now]);
			}
		}
	}

	return false;
}

void solve(){
	cin >>n >>k;
	for(int i=0;i<n;i++){
		cin >>a[i];
	}	
	pii.first=-1,pii.second=-1;
	if(!dfs(0))	puts("-1");	
	else {
		if(pii.first!=-1)	cout <<pii.first <<" " <<pii.second <<endl;
	}
}

int main(){
	int t;
	cin >>t;
	while(t--)	solve();
	return 0;
}

pypy3 解法, 执行用时: 3134ms, 内存消耗: 27796K, 提交时间: 2023-03-12 11:23:11

def dua(v, k, dep):
    n = len(v)
    p = None
    for i in range(n):
        if abs(v[i] - v[(i + 1) % n]) > k:
            p = i
    if p == None:
        return []
    if dep == 0:
        return None
    for i in [p, (p + 1) % n]:
        for j in range(n):
            w = v[:]
            w[i], w[j] = w[j], w[i]
            r = dua(w, k, dep - 1)
            if r == None:
                continue
            return [[i + 1, j + 1]] + r


for _ in range(int(input())):
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
    ans = dua(v, k, 2)
    if ans == None:
        print(-1)
    else:
        print(len(ans))
        for i in ans:
            print(*i)

详情