https://codeforces.com/contest/1077/problem/D
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array s consisting of nn integers.
You have to find any array t of length k such that you can cut out maximum number of copies of array t from array s.
Cutting out the copy of t means that for each element titi of array t you have to find ti in s and remove it from s. If for some ti you cannot find such element in s, then you cannot cut out one more copy of t. The both arrays can contain duplicate elements.
For example, if s=[1,2,3,2,4,3,1] and k=3 then one of the possible answers is t=[1,2,3]. This array t can be cut out 2 times.
- To cut out the first copy of t you can use the elements [1,2_,3,2,4,3_,1_] (use the highlighted elements). After cutting out the first copy of t the array s can look like [1,3,2,4].
- To cut out the second copy of t you can use the elements [1_,3_,2_,4]. After cutting out the second copy of t the array ss will be [4].
Your task is to find such array t that you can cut out the copy of t from s 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 k (1≤k≤n≤2⋅105) — the number of elements in s and the desired number of elements in t, respectively.
The second line of the input contains exactly nn integers s1,s2,…,sn (1≤si≤2⋅105).
Output
Print k integers — the elements of array t such that you can cut out maximum possible number of copies of this array from s. If there are multiple answers, print any of them. The required array t can contain duplicate elements. All the elements of t (t1,t2,…,tk) should satisfy the following condition: 1≤ti≤2⋅105.
Examples
input
7 3
1 2 3 2 4 3 1
output
1 2 3
input
10 4
1 3 1 3 10 3 7 7 12 3
output
7 3 1 3
input
15 2
1 2 1 1 1 2 1 1 2 1 2 1 1 1 1
output
1 1
Note
The first example is described in the problem statement.
In the second example the only answer is [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 2.
In the third example the array t can be cut out 5 times.
题解：
首先计数
排序
二分寻找最大出现次数
根据最大次数，确定子数组
C++版本一
二分
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int N=200000+100;
int t,n,k;
int s[N],b[N];
struct node{
int x,id;
bool operator <(const node& S)const{
return x>S.x;
}
}a[N];
bool sloved(int mid){
int res=0;
for(int i=1;i<=k;i++){
res+=(a[i].x/mid);
}
if(k<=res) return 1;
return 0;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=N;i++){
a[i].id=i;
}
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
a[s[i]].x++;
}
sort(a+1,a+N-10);
int l=1;
int r=a[1].x;
int mid,ans;
while(l<=r){
mid=(l+r)>>1;
if(sloved(mid)){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
int cnt=0;
for(int i=1;i<=k;i++){
for(int j=1;j<=a[i].x/ans;j++){
b[++cnt]=a[i].id;
if(cnt==k)
break;
}
if(cnt==k)
break;
}
for(int i=1;i<=k;i++){
if(i!=k)
printf("%d ",b[i]);
else
printf("%d\n",b[i]);
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
贪心
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int n,k,jg;
int s,x=0;
struct Node
{
int i;
int w;
}vis[200010];
bool cmp(Node a,Node b)
{
return a.w>b.w;
}
int main()
{
int hgf,flag=0,jj;
scanf("%d%d",&n,&k);
memset(&vis,0,sizeof(Node));
for (int i=1;i<=n;i++)
{
scanf("%d",&s);
vis[s].w++;
vis[s].i=s;
}
sort(vis+1,vis+200003+1,cmp);
//printf("%d %d %d",vis[1].w,vis[2].w,vis[3].w);
for (hgf=vis[1].w;hgf>=1;hgf--)
{
int num=0;
while (num<k)
{
for (jj=1;jj<=n;jj++)
{
jg=vis[jj].w/hgf;
if (jg==0) break;
num+=jg;
if (num>=k) break;
}
if (jj>n) break;
if (jg==0) break;
}
if (num>=k) break;
}
//printf("%d\n",hgf);
for (int ii=1;ii<=n;ii++)
{
if (!k) break;
if (vis[ii].w/hgf!=0)
{
for (int dzb=1;dzb<=vis[ii].w/hgf;dzb++)
{
if (!k) break;
k--;
if (!flag) printf("%d",vis[ii].i),flag=1;
else printf(" %d",vis[ii].i);
}
}
}
printf("\n");
} C++版本三
Let's solve the problem using binary search by the answer. It is easy to see that if we can construct the answer for some number of copies val then we also can do it for val−1. The only thing we need is to write the function can(val) which will say can we cut off valval copies of some array t from s or not.
Let's imagine valval copies of string t as a matrix of size val×k. Obviously, each row of this matrix should be equal to each other row. Let's fill not rows but columns of this matrix. For some element i of s we can easy notice that we can take exactly ⌊cntival⌋ columns containing this element where cnti is the number of such elements in s. So, overall number of columns we can fill in this matrix will be ∑i=12⋅105⌊cntival⌋. If this value is greater than or equal to k then can(val) is true otherwise it is false.
It is easy to construct the answer using all things we described above.
Overall complexity is O(n+|A|logn) where |A| is the size of the alphabet.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200 * 1000 + 1;
int n, k;
vector<int> s, t;
vector<int> cnts(MAX);
bool can(int cnt) {
t.clear();
for (int i = 0; i < MAX; ++i) {
int need = min(cnts[i] / cnt, k - int(t.size()));
for (int j = 0; j < need; ++j) {
t.push_back(i);
}
}
return int(t.size()) == k;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> k;
s = vector<int>(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
for (auto c : s) {
++cnts[c];
}
int l = 0, r = n;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (can(mid)) {
l = mid;
} else {
r = mid;
}
}
if (!can(r)) can(l);
for (auto it : t) cout << it << " ";
cout << endl;
return 0;
}
京公网安备 11010502036488号