結果

問題 No.120 傾向と対策：門松列（その１）
コンテスト
ユーザー codershifth
提出日時 2015-10-12 10:43:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 34 ms / 5,000 ms
コード長 2,421 bytes
コンパイル時間 1,761 ms
コンパイル使用メモリ 170,980 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-21 07:16:14
合計ジャッジ時間 2,260 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

class TrendAndCountermeasures_PineDecorationSequence1 {
public:
    void solve(void) {
            int T;
            cin>>T;
            // O(T*N^2)
            REP(t,T)
            {
                //
                // 5 5 5 5 4 4 4 3 2 9 1
                // [5,4,3] [5,4,2] [5,4,9]  ... 5,1
                //
                // 同じものの数が多いものが残ってしまうと、作れる門松の数が減ってしまう。
                // [5,4,3] [2,9,1] ... 5,5,5,4,4
                //
                // よって数が多いものから貪欲に取っていけばよい。
                //
                int N;
                cin>>N;

                map<int,int> degree;
                REP(i,N)
                {
                    int l;
                    cin>>l;
                    degree.emplace(l,0);
                    ++degree[l];
                }
                priority_queue<int> pq;
                for (auto kv : degree)
                    pq.push(kv.second);

                if (pq.size() < 3)
                {
                    cout<<0<<endl;
                    continue;
                }

                int cnt = 0;
                while (true)
                {
                    // ３つ連続で取り出すことで門松の高さの重複を防ぐ
                    int a = pq.top(); pq.pop();
                    int b = pq.top(); pq.pop();
                    int c = pq.top(); pq.pop();

                    // 竹が足りなくて門松が作れないとき
                    if (c <= 0) // a > b > c の順なので c でチェックすれば十分
                    {
                        cout<<cnt<<endl;
                        break;
                    }
                    ++cnt;
                    // 個数を減らして再度 push
                    pq.push(a-1);
                    pq.push(b-1);
                    pq.push(c-1);
                }
            }
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new TrendAndCountermeasures_PineDecorationSequence1();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0