普及二第二题TLE_8分

常规
1 
#include<bits/stdc++.h>

using namespace std;
long long n,k,a[100000009];
bool ch(long long m){
  	long long ssum=0;

	for(long long i=0;i<=n;i++){
		ssum+=min(a[i],m);
    }
	if(ssum<k) return true;
	else return false;
}
int main(){
	cin>>n>>k;
	long long sum=0;
	for(long long i=1ll;i<=n;i++){cin>>a[i];sum+=a[i];}
    
	long long mid,l=0ll,r=k+1ll;
	while(l<r){
		mid=(l+r)>>1ll;

		if(ch(mid)) l=mid+1;
		else r=mid;
	}

	l--; 
	for(long long i=1ll;i<=n;i++){
		if(a[i]>l){
			sum-=l;
			a[i]-=l;
		}else{
			sum-=a[i];
			a[i]=0;
		}

		
	}

	int cnt=1;
	while(sum>0){
		if(a[cnt]>0){
			a[cnt]--;
			
			sum--;
        }
		if(cnt>n){
			cnt=1;
		}
	}
	for(long long i=1ll;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}
2 个赞
2

r改成1e15 k最大才1e9

2 个赞
3

不用了

for(long long i=1ll;i<=n;i++){
		if(a[i]>l){
			sum-=l;
			a[i]-=l;
		}else{
			sum-=a[i];
			a[i]=0;
		}
	}
改成
for(long long i=1ll;i<=n;i++){
		sum+=min(l,a[i]);
		a[i]=max(a[i]-l,1LL-1);
	}
2 个赞
4 
if(a[cnt]>0){
			a[cnt]--;
			
			sum--;
        }
		if(cnt>n){
			cnt=1;
		}
这个改成
while（a[cnt]>0)cnt++;
a[cnt]--;sum--;
cnt++;
3 个赞