PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: ayu_19
Tester & Editorialist: iceknight1093
DIFFICULTY:
2183
PREREQUISITES:
Binary search
PROBLEM:
There are N types of candies, and you have A_i of the i-th type.
Find the maximum number of groups of candies you can make such that:
- Each group contains exactly K candies; and
- Within a group, all candies are distinct
EXPLANATION:
If we can make x groups satisfying the condition, we can certainly make x-1 groups.
This allows us to use binary search to find the largest valid x.
Now, our task switches to the following:
Given x, is it possible to make exactly x groups of candies satisfying the given conditions?
To answer this, let’s look at each of the types of candies.
For the i-th type, we have A_i of them. However, we’re trying to make x groups, and each group can contain at most one of this type.
So, we can only really use \min(x, A_i) candies of type i.
This means the total number of candies usable by us is S_x = \sum_{i=1}^N \min(x, A_i).
Now, since each group should have size K, that means we need x\cdot K candies in total.
So, if S_x \lt x\cdot K, then surely making x groups is impossible.
On the other hand, if S_x \geq x\cdot K, it’s not very hard to see that making x groups is possible (since we have at most x of each type now).
This gives us a check in \mathcal{O}(N) for the binary search: compute S_x = \sum_{i=1}^N \min(x, A_i), and compare it against x\cdot K.
TIME COMPLEXITY
\mathcal{O}(N\log {\left(\sum A_i\right)}) per testcase.
CODE:
Author's code (C++)
#include "bits/stdc++.h"
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template<class T> using oset = tree<T,null_type,less_equal// for indexed_multiset */
// <T> ,rb_tree_tag,tree_order_statistics_node_update> ; // order_of_key (k) -> # of elem strictly < k .
// // *(s.find_by_order(k)) -> element at index K .
#define int long long
using ll= long long;
#define ld long double
#define endl '\n'
#define dbg(x) cout<<#x<<" is -> "<<x<<endl
#define speed_ ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define pb push_back
#define po pop_back
#define mp make_pair
#define sab(x) x.begin(),x.end()
#define rsab(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define sp(x) fixed<<setprecision(x)
#define uni(edge) edge.erase(unique(edge.begin(),edge.end()),edge.end());
#define to_up(x) transform(sab(x),x.begin(),::toupper)
#define to_low(x) transform(x.begin(),x.end(),x.begin(),::tolower)
const int M = 1000000007;
const int MM = 998244353;
const ld Pi= acos(-1);
const int N=1e6+5;
const int inf=1e18;
void simp(){
// dp?, graph?, bs on answer?, compress/sort queries/array?, stupid observation?
int m;
cin>>m;
int n;
cin>>n;
vector<int>a(m);
int sum=0;
for(int i=0;i<m;i++){
cin>>a[i];
sum+=a[i];
}
if(n>m){
cout<<0<<endl;
return ;
}
int l=1;
int r=(sum+n-1)/n;
r+=2;
while(l+1<r){
int mid=(l+r)/2;
int req=mid*n;
for(int i=0;i<m;i++){
req-=min(mid,a[i]);
if(req<=0)break;
}
if(req<=0){
l=mid;
}
else r=mid;
}
cout<<l<<"\n";
}
signed main(){
speed_;
// freopen("input06.txt", "r", stdin);
// freopen("ouput06.txt", "w", stdout);
int t;
t=1;
cin>>t;
int curr=1;
while(t--){
// cout<<"Case #"<<curr++<<": ";
simp();
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
lo, hi = 0, sum(a)//k + 1
while lo+1 < hi:
mid = (lo + hi)//2
have, need = 0, mid * k
for x in a: have += min(x, mid)
if have >= need: lo = mid
else: hi = mid
print(lo)