No.120 傾向と対策：門松列（その１）

貪欲法。
priority_queue から使える竹の数が多いもの順に取り出すのだけど、取り出すときに3つ連続して取り出して、減らして再度 push することでうまく処理する。勉強になった。

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);
                }
            }
    }
};