陈浩轩2愣子

include<bits/stdc++.h>

using namespace std; int n,r,q; struct p{

int id,sc,po;

}; p a[200001],w[200001],l[200001]; int cmp(p s1,p s2){

if(s1.sc!=s2.sc) return s1.sc>s2.sc;
else return s1.id<s2.id;

} void sw(int n){

int i,j,k;
for(k=1,i=1,j=1;k<=n;k++){
	if(a[2*k-1].po>a[2*k].po){
		a[2*k-1].sc++;
		w[i++]=a[2*k-1];
		l[j++]=a[2*k];
	} 
	else{
		a[2*k].sc++;
		w[i++]=a[2*k];
		l[j++]=a[2*k-1];
	}
}
for(k=1,i=1,j=1;i<=n&&j<=n;k++){
	if(cmp(w[i],l[j])) a[k]=w[i++];
	else a[k]=l[j++];
}
while(i<=n) a[k++]=w[i++];
while(j<=n) a[k++]=l[j++];

} int main(){

cin>>n>>r>>q;
for(int i=1;i<=2*n;i++){
	cin>>a[i].sc;
	a[i].id=i;
} 
for(int i=1;i<=2*n;i++) cin>>a[i].po;
sort(a+1,a+1+2*n,cmp);
for(int i=1;i<=r;i++) sw(n);	
cout<<a[q].id;
return 0;

}

评论:

//#include<bits/stdc++.h> using namespace std; int n,m,a[1005][105],vis[1005][105]; int dir[5][3]={{0,1},{0,-1},{1,0},{-1,0}}; void dfs(int x,int y,int sum,int f){

if(sum>=vis[x][y]) return;
else vis[x][y]=sum;
for(int i=0;i<4;i++){
	int xx=x+dir[i][0];
	int yy=y+dir[i][1];
	if(a[xx][yy]==0&&a[x][y]==1||a[xx][yy]==1&&a[x][y]==0) dfs(xx,yy,sum+1,1);
	else if(a[xx][yy]==-1&&f==1){
		a[xx][yy]=a[x][y];
		dfs(xx,yy,sum+2,0);
		a[xx][yy]=-1;
	}else if(a[xx][yy]==a[x][y]) dfs(xx,yy,sum,1);
}

} int main(){

cin>>m>>n;
for(int i=1;i<=m;i++)
	for(int j=1;j<=m;j++)
		vis[i][j]=INT_MAX;
int x,y,z;
memset(a,-1,sizeof(a));
for(int i=1;i<=n;i++){
	cin>>x>>y>>z;
	a[x][y]=z;
}
dfs(1,1,0,1);
if(vis[m][m]==INT_MAX) cout<<"-1";
else cout<<vis[m][m];
return 0;

}

陈浩轩 • 1年前