题目描述
https://codeforces.com/contest/1972/problem/C
算法1
差分
如何使得分数最大?这要看k用完后多余的牌种数
k的用法:
尽量让数组中整体差值最小,比如2 4 7,k=6时,k分4给2,分2给4,此时数组为6 6 7
差值最小,k也要用完
最后k用完时,最小的牌种是多少就可以凑出多少副完整的牌,然后用公式算排列数,再加上多余的牌种,就是答案
为什么?
比如1 2 3 4 5
k使得数组差值最小,k用完时
1有6张
2有4张
3有6张
4有4张
5有7张
最小的牌种的牌数是4,可以凑出4副完整的牌,公式是mminn-n+1;
但1多2张,3多2张,5多3张
那么整体的牌的排列方法是把多余的牌放前面(每个牌种放一张就行),然后肯定不能凑出一副完整的牌,此时用那4副完整的牌凑完整,即135(多余的)24(完整的),13524,
就按照这个排序排完完整的牌,完整的牌本来就有mminn-n+1,再加上前面的135,所以加3
#include <iostream>
//#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <deque>
#include <iomanip>
#include <queue>
#include <utility>
#include <unordered_map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define endl '\n'
#define buff ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
const int N = 200010;
ll a[N];
ll b[N];
void insert(ll l, ll r, ll c)
{
b[l] += c;
b[r + 1] -= c;
}
void solve()
{
ll n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) insert(i, i, a[i]);
for (int i = 2; i <= n; i++)
{
if (k == 0) break;
if (a[i] > a[i - 1])
{
ll ca = a[i] - a[i - 1];
if (k >= ca * (i - 1))
{
k -= ca * (i - 1);
insert(1, i - 1, ca);
}
else
{
int ze = k / (i - 1);
int yu = k % (i - 1);
if (ze) insert(1, i - 1, ze);
insert(1, yu, 1);
k = 0;
}
}
}
ll mmin = 1e12 + 10;
ll ans = 0;
for (int i = 1; i <= n; i++) b[i] += b[i - 1];
for (int i = 1; i <= n; i++) mmin = min(mmin, b[i]);
for (int i = 1; i <= n; i++) if (b[i] > mmin) ans++;
cout << mmin * n - n + 1 + ans + k << '\n';
memset(b, 0, sizeof(b));
}
int main()
{
ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}