二分问题

lsmCC

1. #include <bits/stdc++.h>
   
2. #define int long long
   
3. using namespace std;
   
4. typedef long long ll;
   
5. const int N=2e5+10;
   
6. int n,k;
   
7. int a[N];
   
8. 
   
9. bool check(int mid)
   
10. {
    
11.     ll ans=0;
    
12.     for(int i=1;i<=n;i++)
    
13.     {
    
14.         if(mid>a[i])
    
15.         {
    
16.             ans+=mid-a[i];
    
17.         }
    
18.     }
    
19.     return ans>=k;
    
20. }
    
21. signed main()
    
22. {
    
23.     int t;
    
24.     cin>>t;
    
25.     while(t--)
    
26.     {
    
27.         // int n,k;
    
28.         cin>>n>>k;
    
29.         for(int i=1;i<=n;i++)
    
30.         {
    
31.             cin>>a[i];
    
32.         }
    
33.         ll l=0,r=1e10+10;
    
34.         while(l+1<r)
    
35.         {
    
36.             ll mid=l+r>>1;
    
37.             if(check(mid)) r=mid;
    
38.             else l=mid;
    
39.         }
    
40.         cout<<r<<endl;
    
41. 
    
42.     }
    
43. }

复制代码

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)
        {
            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官方接口），如未能正确解答您的问题，请继续追问。