题解：CF1896G Pepe Racing · Zhl2010 第二博客

CF1896G Pepe Racing。

这道题是让我们把从快到慢的除了那 $n-1$ 个数的数排序。

容易想到，我们一开始肯定是先分成 $n$ 个栈，然后取出每个栈的最大值的比较，找出当前最大值。我们需要维护每一个栈当前的最大值，每当有一个数被取出，都需要重新把这个栈用别的栈中不是最大值的数填满，然后询问最大值。

这样循环，我们最后需要 $2n^2-n+1$ 场比赛，我们需要优化。

我们尝试把一些需要两次查询的改成只需要一次。我们考虑在最后剩下 $2n-1$ 个数的时候的情况，因为这种情况我们无法从别的栈中找到足够的不是最大值的数。

这种情况中，有 $n$ 个数在自己的那个块内当最大值，还有 $n-1$ 个数是“凑数”的，永远不会被选中，所以我们要考虑在 $n$ 次确定这 $n$ 个数的排序。

方法就是每次选这 $n$ 个数没有被选中的加入询问集合，剩下的用那 $n-1$ 个中的一些补全缺口，然后每次拿出最大的，循环直到这 $n$ 个数只剩一个。

注意：如果你不用 set 写法，需要小心当前栈的数去别的栈当最大值，需要注意这种情况。虽然我就是用的 set。

代码

C++

#include<bits/stdc++.h>
using namespace std;
int n;
set<int>s[22];
int query(set<int>&s){
	cout<<"? ";
	for(int j:s)cout<<j<<' ';
	cout<<endl;cout.flush();
	int res;cin>>res;
	return res;
}
int mx[22],u[22];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)s[i].clear();
	for(int i=1;i<=n*n;i++)s[(i-1)/n+1].insert(i);
	for(int i=1;i<=n;i++){
		mx[i]=query(s[i]);
	}
	vector<int>ans;
	for(int i=n*n;i>=2*n;i--){
		set<int>now;
		for(int j=1;j<=n;j++)now.insert(mx[j]);
		int Max=query(now);
		ans.push_back(Max);
		int id=0;
		for(int j=1;j<=n;j++)if(mx[j]==Max){id=j;break;}
		s[id].erase(Max);
		for(int j=1;j<=n;j++){
			if(s[id].size()>=n)break;
			if(j==id)continue;
			for(int k:s[j])if(k!=mx[j]){
				s[id].insert(k);
				s[j].erase(k);
				if(s[id].size()>=n)break;
			}
			if(s[id].size()>=n)break;
		}
		mx[id]=query(s[id]);
	}
	for(int i=1;i<=n;i++)u[i]=0;
	for(int i=1;i<n;i++){
		set<int>now;
		for(int j=1;j<=n;j++)if(!u[j])now.insert(mx[j]);
		if(now.size()<n){
			for(int j=1;j<=n;j++){
				for(int k:s[j])if(k!=mx[j]){
					now.insert(k);
					if(now.size()>=n)break;
				}
				if(now.size()>=n)break;
			}
		}
		int Max=query(now);
		ans.push_back(Max);
		int id=0;
		for(int j=1;j<=n;j++)if(mx[j]==Max){id=j;break;}
		u[id]=1;
		
	}
	for(int j=1;j<=n;j++)if(!u[j]){
		ans.push_back(mx[j]);break;
	}
	cout<<"! ";
	for(int i:ans)cout<<i<<' ';
	cout<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	
	
	return 0;
}