求助大神!!!前缀和+二分却只有30分!?
查看原帖
求助大神!!!前缀和+二分却只有30分!?
677514
Frodo楼主2022/7/24 19:30

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1000100;
int n,k,a[N],l,r,mid,ll,rr;
LL sum[N],tmp,ans=0;
int main() {
	cin>>n>>k;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		sum[i]=(LL)sum[i-1]+(LL)a[i];
	}
	for(int i=1; i<=n; i++) {
		l=i;
		r=n;
		while(l<=r) {
			mid=(l+r)/2;
			if(sum[mid]-sum[i-1]>=k) r=mid-1;
			else l=mid+1;
		}
		if(sum[r]-sum[i-1]<=k&&sum[r]-sum[i-1]>ans) {
			ll=i;
			rr=r;
			ans=sum[r]-sum[i-1];
		}
	}
	printf("%d %d %lld\n",ll,rr,(LL)ans);
	return 0;
}
2022/7/24 19:30
加载中...