yukicoder No.647 明太子
問題
買う人が求める辛さ以上、価格以下を満たす明太子が買われていくとき、一番多く買われた明太子の数を求める。
解法
先に買う人に関する情報が与えられて、次に明太子の情報が入力される。
まずは各入力を配列に格納した後、買われる明太子の数を格納するカウント配列(以下ではcount[ ])も作ろう。
次に2重ループを回して( Xj <= Ai && Bi <= Yj )が真であれば、j番目の明太子が買う人が求める明太子の条件と一致しているのでcount[j]を増やそう。
このような操作は全探索になるため計算量は(NM)になるが、この問題では最悪計算量は10^7になるので間に合う。
以上のような操作を終えれば、求める明太子は一番買われた明太子、つまりcount[ ]の最大値を要素に持つような添字の明太子になる。
最後に、答えとなる明太子が複数ある場合があることに注意しよう。このため、count[ ]の最大値を求めた後、「最大値の要素を持つような添字+1」をすべて出力する必要がある。つまりcount[ ]は2周見る必要がありそうだ。
コードでは、最大値は「maxx」としている。
また、明太子が何も選ばれないこともある。ここで、明太子が何か一つでも選ばれた時点で、count[ ]のどれかの要素は1以上になるので、maxxを求めれば必ず1以上になる。明太子が選ばれない時、maxxは0のままだ。このような時、0を出力しよう。
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; }