yukicoder No.647 明太子

問題

No.647 明太子 - yukicoder

買う人が求める辛さ以上、価格以下を満たす明太子が買われていくとき、一番多く買われた明太子の数を求める。

解法

先に買う人に関する情報が与えられて、次に明太子の情報が入力される。

まずは各入力を配列に格納した後、買われる明太子の数を格納するカウント配列（以下ではcount[ ])も作ろう。

次に２重ループを回して( Xj <= Ai && Bi <= Yj )が真であれば、j番目の明太子が買う人が求める明太子の条件と一致しているのでcount[j]を増やそう。

このような操作は全探索になるため計算量は（NM）になるが、この問題では最悪計算量は10^7になるので間に合う。

以上のような操作を終えれば、求める明太子は一番買われた明太子、つまりcount[ ]の最大値を要素に持つような添字の明太子になる。

最後に、答えとなる明太子が複数ある場合があることに注意しよう。このため、count[ ]の最大値を求めた後、「最大値の要素を持つような添字＋１」をすべて出力する必要がある。つまりcount[ ]は２周見る必要がありそうだ。
コードでは、最大値は「maxx」としている。

また、明太子が何も選ばれないこともある。ここで、明太子が何か一つでも選ばれた時点で、count[ ]のどれかの要素は１以上になるので、maxxを求めれば必ず１以上になる。明太子が選ばれない時、maxxは０のままだ。このような時、０を出力しよう。

int main() {
    int n,m;
    cin>>n;
    vector<int> A(n),B(n);
    rep(i,0,n)cin>>A[i]>>B[i];
    cin>>m;
    vector<int> X(m),Y(m);
    rep(i,0,m)cin>>X[i]>>Y[i];
    
    vector<int> count(m,0);
    rep(i,0,n){
        rep(j,0,m){
            if(X[j]<=A[i]&&B[i]<=Y[j])count[j]++;
        }
    }
    
    int maxx=0;
    rep(i,0,m) maxx=max(maxx,count[i]);
    if(maxx==0){
        cout<<0<<endl;
        return 0;
    }
    rep(i,0,m) if(count[i]==maxx)cout<<i+1<<endl;
    return 0;
}