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

· · 题解

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

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

code

#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();
    }
}