洛谷上的一道砍树问题

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int n,m;
   
4. const int N=1e6+10;
   
5. int a[N];
   
6. void putin()
   
7. {
   
8.     cin>>n>>m;
   
9.     for(int i=1;i<=n;i++)
   
10.     {
    
11.         cin>>a[i];
    
12.     }
    
13. }
    
14. int check(int k)
    
15. {
    
16.     int sum=0;
    
17.     for(int i=1;i<=n;i++)
    
18.     {
    
19.         if(k>a[i])sum+=k-a[i];
    
20.         else sum+=0;
    
21.     }
    
22.     return sum;
    
23. 
    
24. 
    
25. }
    
26. 
    
27. int cut()
    
28. {
    
29.     int l=1,r=1e9;
    
30.     while(l<=r)
    
31.     {
    
32.         int mid=l+r>>1;
    
33.         if(check(mid)>m)l=mid+1;//取多了，将H提高，保证是那个值
    
34.         else if(check(mid)<m)r=mid-1;
    
35.         else
    
36.         {
    
37.         return mid;
    
38.         return 0;
    
39.         }
    
40.         
    
41.     }
    
42.     return r;
    
43.    
    
44. }
    
45. int main()
    
46. {
    
47.     putin();
    
48.     cout<<cut()<<endl;
    
49. 
    
50. }

复制代码

我的cut()里面的代码不对，应该怎么修改呢

isdkz

你需要在cut()函数中做一些修改。在当前的代码中，你在while循环中使用二分查找来寻找满足条件的最小值。但是在找到满足条件的值后，你直接返回了该值，而没有考虑到可能存在多个满足条件的值。

你需要修改cut()函数中的代码，使得它可以找到满足条件的最小值，并返回该值。你可以使用一个变量来记录满足条件的最小值，然后在循环结束后返回这个最小值。

以下是修改后的cut()函数的代码：

1. int cut()
   
2. {
   
3.     int l=1,r=1e9;
   
4.     int result = -1; // 用来记录满足条件的最小值
   
5.     while(l<=r)
   
6.     {
   
7.         int mid=l+r>>1;
   
8.         if(check(mid)>m)
   
9.             l=mid+1;
   
10.         else if(check(mid)<m)
    
11.             r=mid-1;
    
12.         else
    
13.         {
    
14.             result = mid; // 找到一个满足条件的值
    
15.             r = mid - 1; // 继续向左搜索，找到更小的满足条件的值
    
16.         }
    
17.     }
    
18.     return result;
    
19. }
    

复制代码

通过这样的修改，cut()函数将能够正确地找到满足条件的最小值，并返回该值。