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;
}
この記事が気に入ったらサポートをしてみませんか?