怪物森林 爱琳大陆旅行完毕，后几个超时改用二分方法

问题描述

艾琳大陆之行结束了，他也准备回家了。 为了纪念这次旅行，他决定带一些礼物回来给他的好朋友。

走出怪物森林后，我看到N块石头排成一排。

这些石头非常漂亮，我决定将它们作为礼物赠送。

但这N块石头却被施展了特殊的魔法。

如果要清除石头，必须遵守以下规则。

每次必须连续取2*K个石子，且前K个石子的重量之和小于等于S，后K个石子的重量之和小于等于S。

由于时间有限，我们只能领取一次。

既然你已经找到了聪明的那个，就问他最多能拿走多少块石头。

输入格式

第一行包含两个整数 N 和 S。

第二行包含N个整数，用空格分隔，表示每块石头的重量。

输出格式

第一行输出一个数字，表示可以拿走的最大石头数量。

输入样本

8 3

1 1 1 1 1 1 1 1

样本输出

想法

最初的想法是直接遍历，但是只有第二个数据成功。 不知道为什么第一个数据没有成功，最后几个数据超时了。

#include 
using namespace std;int get(vector<int> nums)
{return 0;
}
int main()
{ios::sync_with_stdio(false);long long  n, m;cin >> n >> m;long long x1 = 0;long long x2 = 0;long long s=0;int flag = 0;vector<int> a(n+1);for(long long i=0;i<n;i++){cin >> a[i];}for (long long i = n/2; i >=1; i --){for (long long j = 0; j <= n / 2 - i; j++){x1 = accumulate(a.begin() + j, a.begin() + i + j, 0LL);if (x1 > m){continue;}x2 = accumulate(a.begin() + i + j, a.begin() + i + i + j, 0LL);if (x2 > m){continue;}else{cout << i * 2;flag = 1;break;}}if (flag == 1){break;}}return 0;
}

使用二进制方法代替超时

#include 
#include 
#include 
using namespace std;
const int M = 1e6+5;
int N;long long S;
long long val[M], a[M]; //前缀和，石子每个的质量
bool check(int mid)
{for (int i = mid; i <= N-mid; i++){if (val[i] - val[i - mid] <= S && val[i + mid] - val[i] <= S){return true; //存在符合情况的}}return false;
}
int main()
{cin >> N >> S;for (int i = 1; i <= N; i++){cin >> a[i];val[i] = val[i - 1] + a[i]; //求前缀和}//找符合要求的最大值采用二分法int l = 1, r = N;while (l < r){int mid = l + r + 1 >> 1; //(l+r)/2，这里mid代表了单个区域所取石子的股数if (check(mid))//成功说明当前区域可取{l = mid;//增大l-》增大下一次的mid}elser = mid - 1;//r减小-》减小下一次的mid}cout << 2 * l << endl;
}