1 条题解

  • 0
    @ 2023-12-16 18:14:24

    解题思路: 1.关于二分的对象的上限:这个也是解题的关键之一,对于二分的上限r,我们假设每个颜色的积木,他们的个数是一样的,那么r=各个颜色的积木的和除以k。 比如说,n=4,k=2,而各个颜色的积木的和为10,那么10/2=5,就是假设了一共有5组答案,每组有两个颜色不同的积木.

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long 
    vector<int>nums;
    
    
    int l=1;
    int sum=0;
    int F( int k,int n,int r ){
        r=r/k;
        while( l<r){
            int mid=(l+r+1)>>1;
            for( int i=0;i<n;i++ ){
                if( nums[i]>mid ) sum+=mid;
                else sum+=nums[i];
            }
            int temp=mid*k;
            if( sum>=temp ) l=mid;
            else r=mid-1;
            sum=0;
        }
        return l;
    
    }
    
    
    signed main(){
        int n,k;
        cin>>n>>k;
        
        int r=0;
        int t=0;
        for( int i=0;i<n;i++ ){
            cin>>t;
            nums.push_back(t);
            r+=t;
        }
    
        int ans=F( k,n,r );
        cout<<ans;
    
    
    
    
    
    
    
    
    
    
    }
    
    
    
    
    

    信息

    ID
    2011
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    54
    已通过
    7
    上传者