У вас есть несколько карт. На каждой карте написано целое число от 1 до n: в частности,…
- User
У вас есть несколько карт. На каждой карте написано целое число от 1 до n: в частности, для каждого i от 1 до n у вас есть ai карт, на которых написано число i
.
Также существует магазин, в котором продается неограниченное количество карт каждого типа. У вас есть k монет, поэтому вы можете купить в общей сложности не более k новых карт, и карты, которые вы покупаете, могут содержать любые целые числа от 1 до n
, включительно.
После покупки новых карт вы должны разбить все свои карты на колоды согласно следующим правилам:
все колоды должны иметь одинаковый размер; нет пары карт с одинаковым числом в одной колоде.Найдите максимально возможный размер колоды после покупки карт и их оптимального разбиения. Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число t (1≤t≤104
) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа n , k (1≤n≤2⋅105, 0≤k≤1016
) — количество различных типов карт и количество монет.
Вторая строка каждого набора входных данных содержит n целых чисел a1,a2,…,an (0≤ai≤1010, ∑ai≥1) — количество карт типа i, имеющихся у вас в начале, для каждого 1≤i≤n
.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2⋅105
. Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможный размер колоды при оптимальных действиях. Пример Входные данные Скопировать
9 3 1 3 2 2 5 4 2 6 1 2 4 2 100 1410065408 10000000000 10 8 7 4 6 6 9 3 10 2 8 7 2 12 2 2 2 70 0 1 1 0 1 3 0 2 1 2 3 1 0 3 3
Выходные данные Скопировать
2 3 1 7 2 2 1 1 2
Примечание
В первом наборе входных данных вы можете купить одну карту с числом 1 , и ваш набор карт станет таким: [1,1,1,1,2,2,3,3]. Вы можете разбить их на колоды [1,2],[1,2],[1,3],[1,3]. Они все имеют размер 2, и все содержат разные значения. Можно показать, что невозможно получить разбиение с колодами размером больше 2, поэтому ответ — 2
.
Во втором наборе входных данных вы можете купить две карты с числом 1 и одну карту с числом 3, и ваш набор карт станет таким: [1,1,1,1,2,2,2,2,2,2,3,3,4,4,5,5,5,5]. Его можно разбить на колоды [1,2,3],[1,2,4],[1,2,5],[1,2,5],[2,3,5],[2,4,5]. Можно показать, что нельзя получить разбиение с колодами размером больше 3, поэтому ответ — 3.
реши на C++ эту олимпиадную задачу. код пиши в олимпиадном стиле, с однобуквенными переменными и без комментариев //
- Assistant
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; while(t--){ ll n,k; cin>>n>>k; vector<ll>a(n); ll sum=0, maxa=0; for(auto &x:a){ cin>>x; sum +=x; if(x > maxa) maxa =x; } ll l=1, r=n, ans=1; while(l <=r){ ll mid = l + (r - l)/2; // Compute ceil(sum / mid) ll t_val = (sum + mid -1)/mid; t_val = max(t_val, maxa); // Compute t_val * mid - sum // Check if t_val * mid - sum <=k if(t_val > 1e18 / mid){ // Overflow, set to k+1 to make it invalid if(k < 1e18){ // Some large number // t_val * mid - sum would be >k // so set condition to false r = mid -1; continue; } } ll need = t_val * mid - sum; if(need <=k){ ans = mid; l = mid +1; } else{ r = mid -1; } } cout<<ans<<"\n"; } }