33OJ
登录 注册

2 条题解

  • 2
    @ 2026-11-6 22:57:24精华

    题意

    有 nn 个人,每个人的分数为 aia_i。

    找到一个数 kk,使每位同学的分数变为 max⁡(0,ai−k)\max(0,a_i-k),我们要在新分数之和 sum>msum > m的时候使 kk 变得尽可能的大。

    如果没有符合要求的答案输出 -1。

    思路

    首选二分,因为有个大有个小。我们可以创建一个函数来判断当前的 kk,是否能让 sum>msum>m。但如果刚开始 sum<msum<m,则输出可怜的 -1。 然后二分,但 rr 取值为多少呢?我们取个极限值 10910^9。

    接下来判断当前的 midmid 在函数里的布尔值是否为真,真则答案转向他,让整体值增大 11,否则整体缩小 11。

    温馨提示:

    注意数据范围需开 long long。

    NODE:

    #include <bits/stdc++.h>
    using namespace std;
    int n,a[1000006];
    long long m;
    bool check(long long k){
        long long s=0;
        for(int i=1;i<=n;i++){
            if(a[i]>k)s+=a[i]-k;
        }
        return s>=m;
    }
    int main(){
        cin>>n>>m;
        long long sum=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum+=a[i];
        }
        if(sum<m){
            cout<<-1;
            return 0;
        }
        long long l=0,r=1000000000,ans=0;
        while(l<=r){
            long long mid=(l+r)/2;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        cout<<ans;
    }
    
    • 2
      @ 2026-11-4 22:49:02

      题解

      其实就是一个二分答案,很简单,不过要注意判-1,还有就是每个同学的分数是直接变化的,所以要跑一遍 nn ,当然也可以中途加优化,没啥好说的。

      std

      #include<bits/stdc++.h>
      #define int long long
      using namespace std;
      int n,m;
      int a[1000005]; 
      bool check(int k){
      	int res=0;
      	for(int i=1;i<=n;i++){
      		res+=max(0LL,a[i]-k);
      		if(res>=m) return true;
      	}
      	return res>=m;
      }
      signed main(){
          ios::sync_with_stdio(false);
          cin.tie(0);
      	cin>>n>>m;
      	for(int i=1;i<=n;i++) cin>>a[i];
      	int l=0,r=1000000000LL,ans=-1;
      	while(l<=r){
      		int mid=(l+r)/2;
      		if(check(mid)){
      			ans=mid;
      			l=mid+1;
      		}
      		else r=mid-1;
      	}
      	cout<<ans;
          return 0;
      }
      
      
      • 1

      信息

      ID
      4
      时间
      1000ms
      内存
      512MiB
      难度
      显示难度普及
      标签
      递交数
      5
      已通过
      4
      上传者