Codeforces Round #521 (Div. 3) D. Cutting Out 好题字符串

D. Cutting Out

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array ss consisting of nn integers.

You have to find any array tt of length kk such that you can cut out maximum number of copies of array tt from array ss.

Cutting out the copy of tt means that for each element titi of array tt you have to find titi in ss and remove it from ss. If for some titi you cannot find such element in ss, then you cannot cut out one more copy of tt. The both arrays can contain duplicate elements.

For example, if s=[1,2,3,2,4,3,1]s=[1,2,3,2,4,3,1] and k=3k=3 then one of the possible answers is t=[1,2,3]t=[1,2,3]. This array tt can be cut out 22 times.

• To cut out the first copy of tt you can use the elements [1,2––,3,2,4,3––,1––][1,2_,3,2,4,3_,1_] (use the highlighted elements). After cutting out the first copy of tt the array ss can look like [1,3,2,4][1,3,2,4].
• To cut out the second copy of tt you can use the elements [1––,3––,2––,4][1_,3_,2_,4]. After cutting out the second copy of tt the array ss will be [4][4].

Your task is to find such array tt that you can cut out the copy of tt from ss maximum number of times. If there are multiple answers, you may choose any of them.

Input

The first line of the input contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the number of elements in ss and the desired number of elements in tt, respectively.

The second line of the input contains exactly nn integers s1,s2,…,sns1,s2,…,sn (1≤si≤2⋅1051≤si≤2⋅105).

Output

Print kk integers — the elements of array tt such that you can cut out maximum possible number of copies of this array from ss. If there are multiple answers, print any of them. The required array tt can contain duplicate elements. All the elements of tt (t1,t2,…,tkt1,t2,…,tk) should satisfy the following condition: 1≤ti≤2⋅1051≤ti≤2⋅105.

Examples

input

Copy

7 3
1 2 3 2 4 3 1

output

Copy

1 2 3

input

Copy

10 4
1 3 1 3 10 3 7 7 12 3

output

Copy

7 3 1 3

input

Copy

15 2
1 2 1 1 1 2 1 1 2 1 2 1 1 1 1

output

Copy

1 1

Note

The first example is described in the problem statement.

In the second example the only answer is [7,3,1,3][7,3,1,3] and any its permutations. It can be shown that you cannot choose any other array such that the maximum number of copies you can cut out would be equal to 22.

In the third example the array tt can be cut out 55 times.

题意：给你n个数，寻找k个出现次数最多的数。

分析：

巧妙利用题意），但是会发现有一个错误就是一个数重复的次数过多，可以当两次用，然后这就需要一个东西了，就是这个数抽取m个数的循环次数，看着代码，手推一下就?。

AC：390ms

#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>

using namespace std;

const int N = 200005;

int n, k, a[N], vis[N];
vector< pair<int, int> > ans;
bool cmp(pair<int ,int > x,pair<int ,int > y)
{
    if(x.first==y.first)
    {
        return x.second<=y.second;
    }
    return x.first>=y.first;
}  
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        vis[a[i]]++;
    }
    if(k==1)  //注意这里，不加这一个优化会超时，下面有更快的办法
    {
        int maxx=0,ans=0;
        for(int i=0;i<n;i++)
        {
            if(maxx<vis[a[i]])
            {
                maxx=max(maxx,vis[a[i]]);
                ans=a[i];
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j <= vis[i]; ++j) {///核心思想
            //cout<<i<<" "<<vis[i]/j<<endl;
            ans.push_back({vis[i]/j,i});
        }
    }
    sort(ans.begin(), ans.end(),cmp);
    //reverse(ans.begin(), ans.end());
     
    for (int i = 0; i < k; ++i) {
        printf("%d ", ans[i].second);
    }
    return 0;
}

AC：90ms

#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>

using namespace std;

const int N = 200005;

int n, k, a[N], vis[N];
vector< pair<int, int> > ans;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        vis[a[i]]++;
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j <= vis[i]; ++j) {///核心思想
            //cout<<i<<" "<<vis[i]/j<<endl;
            ans.push_back({vis[i]/j,i});
        }
    }
    sort(ans.begin(), ans.end());
    reverse(ans.begin(), ans.end());
     
    for (int i = 0; i < k; ++i) {
        printf("%d ", ans[i].second);
    }
    return 0;
}

二分待查错误

run time

​​http://codeforces.com/contest/1077/my​​

#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
const int N=1e6+10;
typedef long long I64;
int n,m,k=0;
int v[N];
struct  node
{
    int ID;
    int num;
}vis[N];
bool cmp(node x,node y)
{
    return x.num>=y.num;
}
bool judge(int mid)
{
    int cnt=0;
    for(int i=0;i<k&&vis[i].num>=mid;i++)
    {
        cnt+=vis[i].num/mid;
    }
    return cnt>=m;
}
int serch()
{
    int l=1,r=vis[0].num;
    int ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(judge(mid))
        {
           l=mid+1;
           ans=mid;
        }
        else
            r=mid-1;
    }

    return ans;
}
int main()
{
    I64 maxx=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        I64 x;
        scanf("%I64d",&x);
        v[x]++;
        //cout<<v[a[i]]<<endl;
        if(v[x]==1)
        {
         vis[k].ID=x;
         vis[k].num=1;
         k++;
        }   
        maxx=max(maxx,x);
    }
    for(int i=1;i<=maxx;i++)
    {
        if(v[i]>1)
        {   
        for(int j=0;j<k;j++)
        if(vis[j].ID==i)
        {
            vis[j].num=v[i];
            break;
        }
        }
    }
    sort(vis,vis+k,cmp);
    int num=serch();
    //cout<<num<<endl;
    int x=0;
    for(int i=0;i<k&&x<m;i++)
    {
        int t=vis[i].num;
        //cout<<vis[i].num<<" "<<vis[i].ID<<endl;
        while(t>=num&&x<m)
        {
            t-=num;
            printf("%d ",vis[i].ID);
            x++;    
        }
        if(x>=m) break;
    }
    
    return 0;
}