A40855. 二分法
填空题
困难
知识点
题目描述
二分法
题目描述
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;
typedef long long ll;
const int N = 1e6 + 5;
ll val[N]; //记录重量之和
ll s;
int n;
//该函数的作用是，检查该长度下是否存在符合小于等于S的情况（mid代表其长度）
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() {
int l, r, mid;
ios::sync_with_stdio(false); //取消输入输出缓存，加快cin、cout运算时间
cin >> n >> s;
for (int i = 1; i <= n; i++) {
cin >> val[i];
val[i] += val[i - 1]; //滚动遍历1到i个石子的重量和
}
l = 1; r = n;
while (l <= r) {
mid = (l + r) / 2;
if (Check(mid)) {
l = mid + 1; //该长度下存在符合的连续数，返回l后，
} //mid长度加一，继续寻找更大长度下是否存在
else {
r = mid - 1; //该长度下不存在符合的连续数，返回r后，
} //mid长度减一，继续寻找更小长度下是否存在
}
cout << 2 * r << endl; //r所在的位置就是一边的最大长度
return 0;
}
上一题
下一题