8 条题解

  • 1
    @ 2025-1-19 12:21:22
    // https://dashoj.com/p/89
    #include <bits/stdc++.h>
    
    #define N 1000010
    using namespace std;
    
    typedef long long ll;
    
    ll n, m, ans; // 树木数量 需要木材总长度 答案
    vector<ll> ls; // 输入长度列表
    
    ll addd(int x) {
    	ll re = 0;
    	for (int i = 0; i < n; i++) if (ls[i] > x) re += ls[i] - x;
    	return re;
    }
    
    int main() {
    	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    	cin >> n >> m;
    	for (int i = 0; i < n; i++) {
    		ll a;
    		cin >> a;
    		ls.push_back(a);
    	}
    	sort(ls.begin(), ls.end());
    	ll l = 0, r = ls[n - 1];
    	while (l <= r) {
    		ll mid = (l + r) >> 1;
    		if (addd(mid) < m) r = mid - 1;
    		else {
    			ans = mid;
    			l = mid + 1;
    		}
    	}
    	cout << ans << endl;
    	return 0;
    }
    
    • 1
      @ 2024-4-10 11:04:26
      #include<bits/stdc++.h>
      using namespace std;
      using ll=long long;
      int n;
      const int N=1e6+5;
      ll m,a[N];
      
      bool check(ll mid){
          ll sum=0;
          for(int i=1;i<=n;i++){
              if(a[i]-mid<=0){//如果该树高<=砍树高度,直接跳过
                  continue;
              }
              sum+=(a[i]-mid);
          }
          if(sum>=m){//当sum>=m说明砍树的高度要<=该mid
              return true;
          }
          return false;
      }
      
      int main(){
          cin>>n>>m;
          ll maxx=0;
          for(int i=1;i<=n;i++){
              cin>>a[i];
              maxx=max(maxx,a[i]);
          }
          sort(a+1,a+1+n);//先排序
          ll l=1,r=maxx,ans=0;
          while (r - l > 1) // 当右边界与左边界相差大于1时
      	{
      		int mid = (l + r) >> 1; // 取中间位置
      		if (check(mid)){ // 如果满足条件
                  ans=mid;//最后得到的mid就是答案
      			l = mid; // 更新左边界为mid
              }
      		else{
      			r = mid; // 否则更新右边界为mid
      	    }
          }
          cout<<ans<<endl;
          return 0;
      }
      
      • 0
        @ 2025-4-1 20:58:06
        #include <iostream>
        using namespace std;
        
        int a[1000010];
        
        int main() {
            cin.tie(0);
            cout.tie(0);
        
            long long n, m, max = -1, u = 0, x = 0;
        
            cin >> n >> m;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
                if (max < a[i]) {
                    max = a[i];
                }
            }
        
            long long l = 0, r = max;
        
            while (l <= r) {
                u = 0;
                int mid = (l + r) / 2;
        
                for (int i = 1; i <= n; i++) {
                    if (a[i] > mid) {
                        u += a[i] - mid;
                    }
                }
        
                if (u >= m) {
                    x = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        
            cout << x;
            return 0;
        }
        
        • 0
          @ 2025-3-31 9:08:25
          #include <bits/stdc++.h>
          using namespace std;
          const int N=1e6+10;
          int n,m;
          int a[N];
          
          int main(){
              cin>>n>>m;
              for(int i=1;i<=n;i++){
                  cin>>a[i];
              }
              int l=0,r=2e9;
              while(l<r){
                  int mid=(l+r+1)/2;
                  long long sum=0;
                  for(int i=1;i<=n;i++){
                      if(a[i]-mid>0) sum+=a[i]-mid;
                  }
                  if(sum>=m) l=mid;
                  else r=mid-1;
              }
              cout<<l<<endl;
          }
          
          • 0
            @ 2025-3-15 18:53:17
            #include <bits/stdc++.h>
            #define endl '\n'
            using namespace std;
            typedef pair<int,int> PII;  
            using ll = long long;
            using ULL = unsigned long long;
            const int N = 1e6+5;
            
            ll n ,m, a[N];
            
            bool check(ll mid) {
                ll sum = 0;
                for (int i = 0; i < n; i++) 
                    if (a[i] > mid) sum += a[i] - mid;
                return sum >= m;
            }
            
            inline void solve() { 
                cin >> n >> m;
                ll l = 0, r = 0;
                for (int i = 0; i < n; i++) {
                    cin >> a[i];
                    r = max(r,a[i]);
                }
                while (l < r) {
                    ll mid = (l + r + 1) >> 1;
                    if (check(mid)) l = mid;
                    else r = mid -1;    
                }
                cout << l << endl;
            }          
            
            int main() { 
                ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
                int _ = 1; 
                //int _; cin >> _;
                while (_--) solve();
                return 0;
            }
            
            • 0
              @ 2024-5-25 12:19:20
              def get_wood_amount(trees, cut_height):
                  # 计算砍下的木材总长度
                  wood = sum(tree - cut_height for tree in trees if tree > cut_height)
                  return wood
              
              def find_max_height(trees, m):
                  low, high = 0, max(trees)
                  result = 0
              
                  while low <= high:
                      mid = (low + high) // 2
                      wood = get_wood_amount(trees, mid)
              
                      if wood >= m:
                          result = mid
                          low = mid + 1
                      else:
                          high = mid - 1
              
                  return result
              
              # 读取输入
              n, m = map(int, input().split())
              trees = list(map(int, input().split()))
              
              # 计算结果
              max_cut_height = find_max_height(trees, m)
              
              # 输出结果
              print(max_cut_height)
              
              
              • 0
                @ 2024-4-10 0:30:08

                普普通通二分题 我叫你开longlong你二龙嘛

                #define _CRT_SECURE_NO_WARNINGS 1
                /**
                 * @brief 打开宏开关
                 * */
                #define _USE_MATH_DEFINES
                #include <cmath>
                #include <bits/stdc++.h>
                using namespace std;
                #define ll long long
                
                const int N = 1e6 + 5;
                ll n, m;
                ll a[N];
                bool bisearch(ll h)
                {
                	ll sum = 0;
                	for (int i = 1; i <= n; i++)
                	{
                		if (a[i] > h) sum += a[i] - h;
                	}
                	return sum >= m;
                }
                int main()
                {
                	cin >> n >> m;
                	for (int i = 1; i <= n; i++)
                		cin >> a[i];
                	ll l = 1, r = 1e9;
                	while (l + 1 < r)
                	{
                		ll m = l + r >> 1;
                		if (bisearch(m)) l = m;
                		else r = m;
                	}
                	if (bisearch(l)) cout << l;
                	else cout << r;
                	return 0;
                }
                
                • 0
                  @ 2024-4-9 13:42:37

                  二分答案即可

                  #include <bits/stdc++.h>
                  using namespace std;
                  const int N = 1000010;
                  int a[N];
                  int n,m;
                  int mx = -1;
                  bool check(int x){
                      long long sum = 0;
                      for (int i = 1; i <= n; ++i) {
                          if (a[i] > x) {
                              sum += (a[i] - x);
                          }else{
                              continue;
                          }
                      }
                      if (sum < m) return true;
                      return false;
                  }
                  int main(){
                      scanf("%d %d",&n,&m);
                      for (int i = 1; i <= n; ++i) {
                          scanf("%d",&a[i]);
                          mx = max(mx,a[i]);
                      }
                      int l = 1,r = mx;
                      while (l + 1 < r) {
                          int mid = (l + r)/2;
                          if (check(mid)) {
                              r = mid;
                          }else {
                              l = mid;
                          }
                      }
                      printf("%d\n",l);
                      return 0;
                  }
                  
                  • 1

                  信息

                  ID
                  89
                  时间
                  1000ms
                  内存
                  256MiB
                  难度
                  7
                  标签
                  递交数
                  1686
                  已通过
                  363
                  上传者