求助思路正确性
查看原帖
求助思路正确性
248359
Cloote楼主2022/8/17 17:08

这份代码会在第六个测试点 WA,但调不出来错。所以想知道这种思想是否正确,或者本代码有什么 BUG。

总体而言,就是暴力处理最大值不在队首的情况。处理完后,每一轮肯定是队首赢,就可以输出每个数了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int a[N];
int q[N],fro,las;
int ansi[N];

struct node{
	int id,p,v;
}per[N];

bool cmp(node x,node y){
	return x.v<y.v;
}

int main(){
//	freopen("1.in","r",stdin);
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--){
//		cout<<t<<":\n";
		fro=1,las=0;
		int cnt=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			q[++las]=a[i];
		}
		for(int i=1;i<=m;i++){
			int x;
			cin>>x>>per[i].v;
			per[i].p=a[x];
			per[i].id=i;
		}
		memset(a,0,sizeof(a));
		sort(per+1,per+m+1,cmp);
		int tot=1;
		while(q[fro]!=n){
			int x=q[fro++],y=q[fro++];//取出队首的数
	//		cout<<x<<" "<<y<<"\n";
			if(x<y){
				q[--fro]=y;
				q[++las]=x;
				a[y]++;//存它们赢的轮数
			}
			else{
				q[--fro]=x;
				q[++las]=y;
				a[x]++;
			}
			cnt++;
			while(cnt==per[tot].v) ansi[per[tot].id]=a[per[tot++].p];
		}
		for(int i=tot;i<=m;i++){
			if(per[i].p!=n){
				ansi[per[i].id]=a[per[i].p];
				continue;
			}
			ansi[per[i].id]=a[per[i].p]+per[i].v-cnt;
		}
		for(int i=1;i<=m;i++) cout<<ansi[i]<<"\n";
	}
	return 0;
}
2022/8/17 17:08
加载中...