前提
AtCoder ABC271-C問題で、テストケースの内1つ(03_rnd_01.txt)でWAとなります。その他のテストケースではACです。
実現したいこと
自分の考えた解法を大まかに説明すると、まずa_i~a_Nの要素をListに格納して小さい順にソートします。次に1巻から順に読みたい巻を持っているかListの先頭を見て判断します。Listの先頭が読みたい巻と一致した場合、先頭要素を削除してその巻を読んだことにします。Listの先頭が読みたい巻と一致しなかった場合、List末尾の2要素を削除して読みたい巻を読んだことにします(2冊売って1冊買うという動作に対応)。
これを実装したのが以下のコードです。上で説明していないこともいくつか書いてあります。
該当のソースコード
C++(GCC9.2.1)
1#include <bits/stdc++.h> 2using namespace std; 3int main(){ 4//入力 5 long long N,c,count,buf; 6 cin >> N; 7 list<long long> comic; 8 for(int i=0;i<N;i++){ 9 cin >> c; 10 comic.push_back(c); 11 } 12//入力終わり 13 14 comic.sort(); //小さい順にソート 15 16 count=0; 17 while(1){ 18 19//同じ巻を2冊以上持っていた場合の処理 20//2冊目以降は売ってもいいため、Listの末尾に移動させる 21 for(int i=0;i<comic.size();i++){ 22 if(count==comic.front()){ 23 buf=comic.front(); 24 comic.pop_front(); 25 comic.push_back(buf); 26 }else{break;} 27 } 28 29//読みたい巻を持っているかの判断をする処理 30 if(count+1==comic.front()){ //読みたい巻を持っている場合 31 comic.pop_front(); 32 }else{ 33 if(comic.size()>=2){ //持っていなく、売ることのできる漫画が2冊以上ある場合 34 comic.pop_back(); 35 comic.pop_back(); 36 }else{ //持っていなく、売ることのできる漫画が1冊以下の場合 37 break; 38 } 39 } 40 count++; //何巻まで読んだか記録 41 } 42//例) 43//5 44//1 1 2 2 4 という入力の場合Listとcount挙動は 45// 46//1 1 2 2 4 → 1 2 2 4 → 2 2 4 1 → 2 4 1 → 4 1 2 → 4 → NULL となり、出力は4となる 47//0 → 1 → 1 → 2 → 2 → 3 → 4 48 49 cout << count << endl; 50 51 return 0; 52}

回答1件
あなたの回答
tips
プレビュー
下記のような回答は推奨されていません。
このような回答には修正を依頼しましょう。
また依頼した内容が修正された場合は、修正依頼を取り消すようにしましょう。
2022/10/02 09:00