题目：
牛牛今年上幼儿园了，老师叫他学习减法。老师给了他五个数字，他每次操作可以选择其中的四个数字减一，减一之后的数字不能小于零——因为幼儿园的牛牛还没有接触过负数。
现在牛牛想知道，自己最多可以进行多少次这样的操作？
输入:
2 5 4 3 2 1 1 1 1 10000 1输出:
3 1
这个题数据范围较大，不能使用过于暴力的方法。
考虑到如果可以取x次，那么肯定可以取x-1次，满足二分的单调性，所以尝试二分。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll a[10];
bool ck(ll x)
{
ll s=0;
for(int i=1;i<=5;i++)
if(a[i]<x)
s+=x-a[i];
if(s>x)
return 0;
return 1;
}
int main()
{
int T;
cin >> T;
while(T--)
{
for(int i=1;i<=5;i++)
cin >> a[i];
ll l=1,r=1.3e9;
while(l<r)
{
ll mid=(l+r+1)>>1;
if(ck(mid))
l=mid;
else
r=mid-1;
}
cout << l << endl;
}
}
check函数的原理：
每次选四个减1相当于选一个数不动，剩下的减1，所以考虑每个数最少的不动的次数，a[i]-x如果小于0说明需要某几次不减才能不变成负数，把这个次数做一个计数和x比较即可。
全部评论
(13) 回帖