试题 算法训练 礼物

问题描述

　　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,000S<=10^12每个石子的重量小于等于10^9且非负

#include<iostream>
using namespace std;

long long weight[1000001] = { 0 };
long long prefix[1000001] = { 0 };
int N;
long long S;

bool check(int mid) {
	for (int i = mid; i <= N - mid; i++) {
		if (prefix[i] - prefix[i - mid] <= S && prefix[i + mid] - prefix[i] <= S) {
			return true;
		}
	}

	return false;
}

int main() {
	cin >> N >> S;

	for (int i = 1; i <= N; i++) {
		cin >> weight[i];
		prefix[i] = prefix[i - 1] + weight[i];
	}

	int start = 1, end = N, mid;

	while (start < end) {
		mid = (start + end + 1) / 2;

		if (check(mid) == true) {
			start = mid;
		} else {
			end = mid - 1;
		}
	}

	cout << 2 * start;

	return 0;
}

总结

在main中mid=start+end+1/2时mid一定要+1不然可能要陷入死循环

比如给的例子

当循环到mid=2的时候会陷入死循环因为check返回的是true然后start=2end又等于3

2+3除以2还是等于2所以一定要+1