题解：P13109 [GCJ 2019 #1B] Manhattan Crepe Cart

很容易想到一个做法：统计每个位置有多少人可能要去，最多人想去的就是答案。但是这样时间复杂度

O(Q^2T)

，会炸。

发现每个人可能去的位置是一个区间，统计区间可以用差分和前缀和。分开处理每行和每列有多少人要去。然后找到最多人的行上的最多人的位置，就是答案了。

code

CPP

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int b[100010];
void pp(){
	memset(a,0,sizeof a);
	memset(b,0,sizeof b);
	int n,m;
	cin>>m>>n;
	while(m--){
		int x,y;
		cin>>x>>y;
		char c;
		cin>>c;
		if(c=='N'){
			b[y+1]++;
			b[n+1]--;
		}
		if(c=='S'){
			b[0]++;
			b[y]--;
		}
		if(c=='E'){
			a[x+1]++;
			a[n+1]--;
		}
		if(c=='W'){
			a[0]++;
			a[x]--;
		}
	}
	for(int i=1;i<=n;i++){
		a[i]+=a[i-1];
		b[i]+=b[i-1];
	}
	int mx=-1,mxx,my=-1,myy;
	for(int i=0;i<=n;i++){
		if(a[i]>mx){
			mx=a[i];
			mxx=i;
		}
	}
	for(int i=0;i<=n;i++){
		if(b[i]>my){
			my=b[i];
			myy=i;
		}
	}
	cout<<mxx<<" "<<myy<<endl;
}
int main(){
	int T;
	cin>>T;
	for(int i=1;i<=T;i++){
		cout<<"Case #"<<i<<": ";
		pp();
	}
}

题解：P13109 [GCJ 2019 #1B] Manhattan Crepe Cart

文章操作

code

相关推荐

评论

题解：P13109 [GCJ 2019 #1B] Manhattan Crepe Cart