ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

2267B　Fashionable Array

来源：Codeforces ★ 1200

本题活力0.60按难度、完成结果与训练证据估算

算法如山行则将至

查看原题王梓豪 的主页

题目描述

B. Fashionable Array
time limit per test1 second
memory limit per test256 megabytes
The mode of an array — is the number that appears the maximum number of times in the array. If several numbers appear the maximum number of times, the mode is the largest among them. For example, the mode of the array [1,1,2]
is 1
, and the mode of the array [3,4]
is 4
.

You are given an array a
consisting of n
integers. You may arbitrarily permute the numbers in array a
in any order. Your task — is to rearrange the numbers in array a
so that the sum of the modes over all prefixes of the array is maximized.

For example, the array [2,3,2]
can be rearranged as [3,2,2]
. Then the sum of the modes over all prefixes is determined as follows:

The prefix of length 1
is [3]
. The mode of this prefix is 3
.
The prefix of length 2
is [3,2]
. The mode of this prefix is 3
.
The prefix of length 3
is [3,2,2]
. The mode of this prefix is 2
.
Thus, the sum of the modes is 3+3+2=8
. It can be proven that for this arrangement of array a
, the answer is maximal.
Input
Each test contains multiple test cases. The first line contains the number of test cases t
(1≤t≤500
). The description of the test cases follows.

The first line of each test case contains one integer n
(1≤n≤100
) — the size of the array.

The second line of each test case contains n
integers a1,a2,…an
(1≤ai≤100
) — the elements of the array.

Output
For each test case, output a new array whose sum of the modes over all prefixes is maximal. If there are several optimal answers, output any of them.

代码

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<int> a(n),cnt(101,0);
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            cnt[a[i]]++;
        }
        bool flag=1;
        while(flag)
        {flag=0;
            for(int i=100;i>=0;i--)
        {
            if(cnt[i]>0){cout<<i<<' ';cnt[i]--;flag=1;}
        }
 
    }
    cout<<endl;
    }
}