Codeforces Round #540 (Div. 3) D2. Coffee and Coursework (Hard Version) (二分,贪心)

题意:有\(n\)个数,每次可以选\(k(1\le k\le n)\)个数,并且得到\(a_1+max(0,a_2-1)+max(0,a_3-2)+...+max(0,a_k-k+1)\)的贡献,问最少选多少次使得总贡献不小于\(m\).
题解:我们从大到小排序,然后二分答案,贪心,如果答案是\(k\)天,那么对于前\(k\)个数,我们一定单独选它们分配到不同的\(k\)个集合中,然后再重复这个过程,从\(k+1\)个数开始循环分配到不同j集合中,这样一定能得到最大的贡献.

代码:

ll n,m;

ll a[N];

ll sum;

bool check(ll x){

	ll res=0;

	ll cnt=0;

	ll num=0;

	for(int i=1;i<=n;++i){

		res+=max((ll)0,a[i]-num);

		cnt++;

		if(cnt==x) num++,cnt=0;

	}

	if(res>=m) return true;

	return false;

}

bool cmp(ll a,ll b){

	return a>b;

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n>>m;

    for(int i=1;i<=n;++i){

    	cin>>a[i];

    	sum+=a[i];

    }

    if(sum<m){

    	cout<<-1<<endl;

    	return 0;

    }

    sort(a+1,a+1+n,cmp);

    ll l=1,r=n;

    while(l<r){

    	int mid=(l+r)>>1;

    	if(check(mid)){

    		r=mid;

    	}

    	else l=mid+1;

    }

    cout<<l<<endl;

    return 0;

}

巴特西

Codeforces Round #540 (Div. 3) D2. Coffee and Coursework (Hard Version) (二分,贪心)

最新文章

热门文章