B - Increasing Triples

・問題URL

https://atcoder.jp/contests/arc123/tasks/arc123_b

・発想

・爆死回で解けなかったやつ。もう一回冷静に考えたら解けた。
・とりあえずABCをsortしてもええやろ。

・解法

・Aは出来るだけ小さいの使いたい。
・となるとBのうち、minA以下の要素はもうつかわない。
・次にBもできるだけ小さいの使いたい。
・となるとCのうち、残ってるBの中でのminB以下の要素は使わない。
・条件を満たすCの要素のうち最小なのを取り出してこれで1グループできた。
・これ繰り返せばよさそう。
ABCをsortしてque使ったが、priority_queue(の小さい順に取り出すver)でいいじゃん。やっぱりまだSTLのコンテナ慣れてない。あとやっぱりとりあえずsortしてみるの大事かも

・コード

int main(){

 queue<ll>queA,queB,queC;
 int N;
 cin>>N;
 vector<ll>A(N),B(N),C(N);
 rep(i,N)cin>>A[i];
 rep(i,N)cin>>B[i];
 rep(i,N)cin>>C[i];
 
 sort(A.begin(),A.end());
 sort(B.begin(),B.end());
 sort(C.begin(),C.end());
 
 rep(i,N)queA.push(A[i]);
 rep(i,N)queB.push(B[i]);
 rep(i,N)queC.push(C[i]);
 
 ll ans=0;
 while(!queA.empty()){
 
   ll a=queA.front();
   queA.pop();
   while(a>=queB.front()&&!queB.empty()){
     queB.pop();
   }
   if(queB.empty())break;
   else{
     ll b=queB.front();
     queB.pop();
     while(b>=queC.front()&&!queC.empty()){
       queC.pop();
     }
     if(queC.empty())break;
     else {
       ans++;
       queC.pop();
     }
   }
   
  }
 
 cout<<ans<<endl;
 }

この記事が気に入ったらサポートをしてみませんか?