二分问题

lsmCC

#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[N];

bool check(int mid)
{
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(mid>a[i])
        {
            ans+=mid-a[i];
        }
    }
    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[i];
        }
        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

FishC_GPT

这段代码是一个通过二分法解决的问题。下面我将解释一下它的具体作用和思路。

该问题的目标是找到一个数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[N];

bool check(int mid)
{
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(mid<a[i])
        {
            ans+=mid-a[i];
        }
    }
    return ans>=k;
}

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        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官方接口），如未能正确解答您的问题，请继续追问。