题目描述
输入 $n (1≤n≤2e5)$, $m (1≤m≤1e9)$ 和长为 $n$ 的数组 $a(1≤a[i]≤1e9)$。
把这 $n$ 个数重新排列,然后分成 $x$ 个组。
每个组的第一个数不变,第二个数减一,第三个数减二,依此类推。
如果有数字减成负数,则从组中去掉。
要使所有数字之和至少为 $m$,$x$ 最小是多少?
如果无法做到,输出 $-1$。
样例
输入样例1
5 8
2 3 1 1 2
输出样例1
4
输入样例2
7 10
1 3 4 2 1 4 2
输出样例2
2
输入样例3
5 15
5 5 5 5 5
输出样例3
1
输入样例4
5 16
5 5 5 5 5
输出样例4
2
输入样例5
5 26
5 5 5 5 5
输出样例5
-1
算法1
(二分+贪心) $O(n*log(n))$
我们先考虑在一个组内,一定是从大到小排序,可以证明,假设当前数需要减去$k$,那么一组内将大的数交换到这里,如果原本的数减去$k>=0$,结果不变,但是如果是<$0$的话,这一组的最终结果会减小。所以在一组内的数一定是从大到小。
我们再考虑当组数为$x$时,我们应该怎样分组才能让结果最大,我们发现,在每一组内,越往前的数最后减的数越小,越往后的数最后减的数越大,但是减完后又会和0取较大值,所以我们直觉是让所有的数从大到小依次给到每一组,每一组内大的在前。可以证明,交换不同组的两个数$x1,x2$(同一组不能交换,上面已证),假设这两个数要减掉的数为$k1,k2$,如果$k1==k2$,那么答案不变,如果不相等,假设$k1 < k2$,有$x1 >= x2$,一定有$max(0, x1-k1)+max(0, x2-k2)>=max(0, x1-k2)+max(0, x2-k1)$,所以以上分组可以使答案最大。
下面我们证明答案具有二段性,假设组数为$x1$时不满足条件,那么当组数更小时,总的数加起来不变,但是减的数更多了,所以答案一定在右边。
C++ 代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5+10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int w[N];
bool check(int mid)
{
LL res = 0;
int cnt = -1;
for(int i=n,j=0;i;i--,j++){
if(j%mid==0) cnt++;
res+=max(0, w[i]-cnt);
}
return res>=m;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
sort(w+1, w+n+1);
LL sum = 0;
for(int i=1;i<=n;i++) sum += w[i];
if(sum<m) cout<<-1<<endl;
else{
int l=1, r=n;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r<<endl;
}
return 0;
}