二分问题
#include <bits/stdc++.h>#define int long long
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,k;
int a;
bool check(int mid)
{
ll ans=0;
for(int i=1;i<=n;i++)
{
if(mid>a)
{
ans+=mid-a;
}
}
return ans>=k;
}
signed main()
{
int t;
cin>>t;
while(t--)
{
// int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a;
}
ll l=0,r=1e10+10;
while(l+1<r)
{
ll mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid;
}
cout<<r<<endl;
}
}
https://codeforces.com/contest/1873/problem/E
不知道哪里错了，求指正，有的值比原来的还要多1
这段代码是一个通过二分法解决的问题。下面我将解释一下它的具体作用和思路。
该问题的目标是找到一个数mid，使得满足条件check(mid)=true，并且mid是所有满足条件的数中最小的数。条件check(mid)的实现是遍历数组a，统计大于mid的元素的个数，并累加相差的值。
首先，我们需要输入测试用例的数量t，并循环处理每个测试用例。
在每个测试用例中，我们输入两个数n和k，并读取数组a的元素。接下来，我们需要确定二分的上下界。通常情况下，我们可以将上界设置为数组a中的最大值加上一个较大的数，这里我们将其设置为1e10+10。下界设置为0即可。
然后，我们通过while循环进行二分查找。在每次循环中，我们计算出mid的值，并调用check函数来判断当前mid是否满足条件。若满足，则将r更新为mid；否则，将l更新为mid。最终循环结束时，l的值就是我们要寻找的答案。
最后，我们输出结果。
完整的代码如下：
#include <iostream>
#define int long long
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,k;
int a;
bool check(int mid)
{
ll ans=0;
for(int i=1;i<=n;i++)
{
if(mid<a)
{
ans+=mid-a;
}
}
return ans>=k;
}
signed main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a;
}
ll l=0,r=1e10+10;
while(l+1<r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
cout<<l<<endl;
}
return 0;
}
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。
页:
[1]