結果

問題 No.120 傾向と対策：門松列（その１）
ユーザー ふーらくたるふーらくたる
提出日時 2016-09-16 12:23:40
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 86 ms / 5,000 ms
コード長 1,414 bytes
コンパイル時間 873 ms
コンパイル使用メモリ 80,048 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-17 06:29:23
合計ジャッジ時間 1,856 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
6,816 KB
testcase_01 AC 84 ms
6,816 KB
testcase_02 AC 39 ms
6,816 KB
testcase_03 AC 86 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <map>
#include <utility>
#include <functional>
#include <queue>
#include <vector>
using namespace std;

using Info = pair<int, int>;    // (残存数, 竹の長さ)

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        map<int, int> bamboos;
        for (int i = 0; i < n; i++) {
            int l;
            cin >> l;
            bamboos[l]++;
        }

        priority_queue<Info, vector<Info>, greater<Info>> que;
        int ans = 0;
        while (true) {
            for (auto it = bamboos.begin(); it != bamboos.end(); it++) {
                Info new_info = make_pair(it->second, it->first);
                if (que.size() < 3) {
                    que.push(new_info);
                } else {
                    Info bigger_info = max(new_info, que.top());
                    que.pop();
                    que.push(bigger_info);
                }
            }

            if (que.size() == 3) ans++;
            else break;

            while (!que.empty()) {
                Info info = que.top(); que.pop();
                int len = info.second;
                bamboos[len]--;
                // 竹が存在しなくなったならば削除
                if (bamboos[len] == 0) {
                    bamboos.erase(len);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}
0