题目大意
给出 $n$ 个数,每次把任意 $k$ 个数减去 $1$ ,等于 $0$ 的数不能减,问最多能减几次?
思路
枚举可以减去的次数。
那么如何判断是否能减去 $x$ 次呢?
根据样例一可以画出下图:
我们就先假设 $x=2$ 吧。
对于每一个数,分为两种情况:大于等于 $x$ 和小于 $x$ 。
当这个数大于等于 $x$ 时:
那么这个数减去 $x$ 次是肯定没有问题的了。
计数器加 $1$ 。
这时, $3$ 和 $4$ 就已经被毙掉了,剩个 $2$ 。
有人可能会问: $x$ 明明是 $2$ ,减去后 $3$ 和 $4$ 难道不应该变成 $1$ 和 $2$ 吗?
实际上,当这个数大于等于 $x$ 时,减去和毙掉没什么区别。
因为就算你把这个数减去 $x$ ,它剩下的也没有任何用处了。因为在 $x$ 次减去的过程中,这个数每一次都参与了,没有多出来的机会给剩下的来减。
这个细节其实在纸上模拟一下减去的过程就能想通了。
当这个数小于 $x$ 时:
剩下这些零零碎碎的,全部加起来,最后再看看能够凑出几个 $x$ 来。
于是我们把剩下的所有数加起来,到最后计数器加总和除以 $x$ 就行了。
刚刚已经把 $3$ 和 $4$ 毙掉了,剩下 $2$ 。
加起来的总和是 $2$ ,最后计数器只能加 $0$ 。
最终计数器是 $2$ 。
我们最后只需要判断计数器是否大于等于 $x$ ,如果大于等于的话就是能减去 $x$ 次,否则不能。
故能够减去 $2$ 次。
我们再去看一看数据范围,枚举很明显会超时。
众所周知,二分答案是个好东西。
c++代码
#include<bits/stdc++.h>
#define ll long long//不开long long见祖宗
using namespace std;
int n,c;
ll h[1000100],l=0,r=1e18+1,mid,ans;
bool check(ll x) {
ll sum=0,s=0;
for(int i=1; i<=n; i++) {
if(h[i]>=x) s++;//可以减x次
else sum+=h[i];//零碎的加进去
}
s+=sum/x;//零碎凑出几个x
return s>=c;//x的个数是否符合
}
int main() {
scanf("%d%d",&n,&c);
for(int i=1; i<=n; i++) scanf("%lld",&h[i]);
if(n<c) {
printf("0");
return 0;
}
while(l+1<r) {//二分同时建立项目的个数
mid=(l+r)/2;
if(check(mid)) {
l=mid;
ans=mid;
} else r=mid;
}
printf("%lld",ans);
return 0;
}
10年oi一场空,不开long long见祖宗!