結果

問題 No.120 傾向と対策：門松列（その１）
コンテスト
ユーザー ふーらくたる
提出日時 2016-09-16 12:23:40
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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