P5745【深基附B例】区间最大和

思路一：枚举区间头尾i，j，然后对i和j里面所有数字累加起来求和，再判断是否在不大于M的情况下最大。

#include<iostream>
using namespace std;
int a[8000005];
int main() {
	int n, M, ansm = 0, ai, aj;
	cin >> n >> M;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			int sum = 0;
			for (int k = i; k <= j; k++) {
				sum += a[k];
			}
			if (sum <= M && sum > ansm) {
				ansm = sum;
				ai = i;
				aj = j;
			}
		}
	}
	cout << ai << " " << aj << " " << ansm;
	return 0;
}

结果只有惨不忍睹的10分。

思路二：使用前缀和快速求出区间和。

#include<iostream>
using namespace std;
int a[8000005], s[8000005];
int main() {
	int n, M;
	int ansm = 0, ai, aj;
	cin >> n >> M;
	s[0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			int sum = s[j] - s[i - 1];
			if (sum <= M && sum > ansm) {
				ansm = sum;
				ai = i;
				aj = j;
			}
		}
	}
	cout << ai << " " << aj << " " << ansm;
	return 0;
}

挽救了20分，变成30分。

思路三：还要快（比赛的时候能骗到这些分就够了）该怎么办呢？尝试用二分。

#include<iostream>
using namespace std;
int a[8000005];
long long n,M,s[8000005];
int find(long long x){
	int l=1,r=n+1;
	while(l<r){
		int mid=(l+(r-1))/2;
		if(s[mid]>=x){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	if(s[l]==x){
		return l;
	}else{
		return l-1;
	}
}
int main(){
	long long ansm=0;
	int ai,aj;
	cin>>n>>M;
	s[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		long long x=s[i-1]+M;
		int j=find(x);
		long long sum=s[j]-s[i-1];
		if(sum<=M&&sum>ansm){
			ansm=sum;
			ai=i;
			aj=j;
		}
	}
	cout<<ai<<" "<<aj<<" "<<ansm;
	return 0;
}

终于AC啦。