灵神的每日一题(难度:1600)
题目描述
原题链接 https://codeforces.com/contest/1622/problem/C
You are given an integer array a1,a2,…,an and integer k.
In one step you can
either choose some index i and decrease ai by one (make ai=ai−1);
or choose two indices i and j and set ai equal to aj (make ai=aj).
What is the minimum number of steps you need to make the sum of array ∑i(1~n)=ai≤k? (You are allowed to make values of array negative).
Input
The first line contains a single integer t (1≤t≤1e4) — the number of test cases.
The first line of each test case contains two integers n and k (1≤n≤2*1e5; 1≤k≤1e15) — the size of array a and upper bound on its sum.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤1e9) — the array itself.
It’s guaranteed that the sum of n over all test cases doesn’t exceed 2*1e5.
Output
For each test case, print one integer — the minimum number of steps to make ∑i(1~n)=ai≤k.
样例
输入:
4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10
输出:
10
0
2
7
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;
const int N = 2 * 1e5 + 10;
vector<LL> a;
int t;
LL min(LL a,LL b)
{
return a < b ? a : b;
}
int main()
{
cin >> t;
while(t -- )
{
a.clear();
LL n,k,sum = 0;
cin >> n >> k;
for(int i = 1;i <= n;i++) {
int x;
cin >> x;
sum += x;
a.push_back(x);
}
sort(a.begin(),a.end());
if(k >= sum){
cout<<"0"<<endl;
continue;
}
else{
LL res = sum - k;
LL s = a[0] - res;
for(int i = n - 1;i > 0;i--)
{
s += a[i];
LL x;
int y = n - i + 1;
if(s >= 0) x = s / y;
else x = (s- y + 1) / y;
x = min(x,a[0]);
res = min(res , a[0] - x + y - 1);
}
cout<<res<<endl;
}
}
return 0;
}