资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　JiaoShou在爱琳大陆的旅行完毕，即将回家，为了纪念这次旅行，他决定带回一些礼物给好朋友。
　　在走出了怪物森林以后，JiaoShou看到了排成一排的N个石子。
　　这些石子很漂亮，JiaoShou决定以此为礼物。
　　但是这N个石子被施加了一种特殊的魔法。
　　如果要取走石子，必须按照以下的规则去取。
　　每次必须取连续的2*K个石子，并且满足前K个石子的重量和小于等于S，后K个石子的重量和小于等于S。
　　由于时间紧迫，Jiaoshou只能取一次。
　　现在JiaoShou找到了聪明的你，问他最多可以带走多少个石子。

输入格式

　　第一行两个整数N、S。
　　第二行N个整数，用空格隔开，表示每个石子的重量。

输出格式

　　第一行输出一个数表示JiaoShou最多能取走多少个石子。

样列输入

　　8 3
　　1 1 1 1 1 1 1 1

样列输出

　　6

样列解释

　　任意选择连续的6个1即可。

数据规模和约定

　　对于20%的数据：N<=1000
　　对于70%的数据：N<=100,000
　　对于100%的数据：N<=1000,000，S<=10^12，每个石子的重量小于等于10^9，且非负

---

这道题一定要注意数据的范围

 

看到题目第一个想法就是循环套循环

#include<iostream>
using namespace std;
 
int main() {
	int N;
	long long S;
	cin >> N >> S;
	int *arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	int ans = 0;
	long long weight1 = 0;
	long long weight2 = 0;
	for (int j = 0; j < N; j++) {
		//cout << "第j个数" << j << endl;
		for (int k = 1; k <= (N - j) / 2; k++) {
			weight1 = 0;
			weight2 = 0;
			//cout << "第j个数后可以有K个,k=" << k << endl;
			for (int i = 0; i < k; i++) {
				weight1 += *(arr + i+j);
				weight2 += *(arr + i + k + j);
				
			}
			//cout << "W1=" << weight1 ;
			//cout << ";W2=" << weight2 << endl;
			if (weight1 <= S && weight2 <= S) {
				ans = max(ans, k);
				//cout << "ans=" << ans << endl;
			}
			else {
				break;
			}
		}
	}

	cout << 2 * ans;

	return 0;
}

但是运行超时，就改进了一下，但是只有90分

#include<iostream>
using namespace std;
const int Max = 1e6 + 3;
int main() {
	int N;
	long long S;
	cin >> N >> S;
	int* arr = new int[N];
	long long sum[Max] ;
	cin >> arr[0];
	sum[0] = arr[0];
	for (int i = 1; i < N; i++) {
		cin >> arr[i];
		sum[i] = sum[i - 1] + arr[i];

	}
	int ans = 0;
	for (int j = 0; j < N; j++) {
		//cout << "第j个数" << j << endl;
		for (int k = ans; k <= (N - j) / 2; k++) {

			//cout << "W1=" << weight1 ;
			//cout << ";W2=" << weight2 << endl;
			if (sum[j + k] - sum[j] <= S && sum[j + 2 * k] - sum[j + k] <= S) {
				//cout << "W1=" << sum[j + k] - sum[j];
				//cout << ";W2=" << sum[j + 2 * k] - sum[j + k] << endl;
				ans = max(ans, k);
				//cout << "ans=" << ans << endl;
			}
			else {
				break;
			}
		}
	}
	cout << 2 * ans;
	return 0;
}

最后就去网上看了一下别人的代码，发现大多数都是用二分法做的

#include<iostream>
using namespace std;
const int Max = 1e6 + 10;
long long sum[Max];
int weight[Max];
long long s;
int n;
bool fun(int k) {
	for (int i = k; i <= n - k; i++) {
		if (sum[i] - sum[i - k] <= s && sum[i + k] - sum[i] <= s)
        //当i=k时，计算的是0~2k；当i=n-k时，计算的是n-2k~n
			return true;
	}
	return false;
}
int main() {	
	cin >> n >> s;
	sum[0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> weight[i];
		sum[i] = sum[i - 1] + weight[i];
	}
	int left = 1;
	int right = n / 2;
    //这里right=n也可以
	int k = 0;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (fun(mid)) {
			left = mid + 1;
			k = mid;
		}
		else {
			right = mid - 1;
		}
	}
	cout << 2 * k << endl;
	return 0;
}