結果

問題 No.120 傾向と対策:門松列(その1)
ユーザー なおなお
提出日時 2015-01-08 23:57:09
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 56 ms / 5,000 ms
コード長 1,097 bytes
コンパイル時間 1,267 ms
コンパイル使用メモリ 159,000 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-03 22:45:18
合計ジャッジ時間 1,990 ms
ジャッジサーバーID
(参考情報)
judge14 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 51 ms
4,380 KB
testcase_01 AC 56 ms
4,384 KB
testcase_02 AC 29 ms
4,380 KB
testcase_03 AC 55 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
const int MOD = 1000000007;

int solve(const VI &A){
    int N = A.size();
    map<int,int> m;
    int c = 0;
    REP(i,N) m[A[i]]++;
    priority_queue<pair<int,int> > q;
    FOREACH(it, m){
        q.push(make_pair(it->second, it->first));
    }
    while(1){
        pair<int,int> a[3];
        REP(i,3){
            if(q.size() == 0) return c;
            a[i] = q.top(), q.pop();
        }
        REP(i,3){
            a[i].first--;
            if(a[i].first > 0){
                q.push(a[i]);
            }
        }
        c++;
    }
    return c;
}

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

    REP(i,T){
        int N; cin >> N;
        VI v;
        REP(j,N){
            int a; cin >> a;
            v.push_back(a);
        }
        cout << solve(v) << endl;
    }
    return 0;
}
0