4446: 【基础】不太甜的糖果(2105)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
小Y走啊走啊，翻山越岭、跋山涉水，终于，小Y累了。虽然，糖果的诱惑强大，但他的两条腿已经不听使唤，只能坐在地上叹气，内心无比焦急……
突然眼前一黑，小Y没有昏过去，但是眼前出现了一个糖人。在这无人之地，小Y没有别的办法，只得求助糖人。
善良的糖人没法拒绝小Y的请求，但还要遵守这个世界的规则，所以，小Y不能”不劳而获”，但小Y现在已经没有力气。糖人只让他玩一个小小的游戏，完成这个游戏，小Y才能获得补充能量，继续前进。
但是，小Y满脑子都是糖果，他没有心思玩游戏，只想着吃糖。所以，他向你求助。
游戏的规则是这样的： 给定一排长度为 的糖果串，每个糖果有一个甜度；在不改变糖果顺序的前提下，求出一个最短的糖果串使得它的甜度之和大于等于 。
输入
第一行包含两个数 和 ，第二行有 个数。
输出
输出一行，包含一个数，即最短的糖果串的长度；如果找不到这样的糖果串，输出 。
样例输入 复制
10 15
5 1 3 5 10 7 4 9 2 8 样例输出 复制
2提示
【样例说明】
糖果串为连续的。
对于样例数据，选第四五个可以达到 或者第五六个能达到 ，所以最短糖果串为 。
【数据范围】
对于 的数据，
对于 的数据，
对于 的数据，
对于 的数据，
对于 的数据，
，糖果的甜度为正整数，且本题数据保证连续若干糖果的甜度和在int范围内。
#include<bits/stdc++.h>
using namespace std;
/*
给定一排长度为n的糖果串，每个糖果有一个甜度，
求出一个最短的糖果串使得它的甜度之和大于等于m。
给定一个数组，求最短的子串，使得元素之和>=m。
解题关键:
1.二分可能的长度
2.用前缀和求区间和
*/
const int N=230010;
int a[N],f[N]; //f:代表前缀和
int n,m;
//检验子串长度为mid 的情况下，子串和是否可能>=m
bool check(int mid) {
//从每个可能的开头开始求连续mid个数的和
for(int i=1;i<=n- mid + 1;i++){ //区间范围:i~i+mid-1
if(f[i+mid-1]-f[i-1]>=m)
return true;
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<= n;i++){
cin>>a[i];//求前缀和
f[i]= f[i-1]+ a[i];
}
//如果所有数的和都不满足>=m，则无解
if(f[n]< m){
cout<<0;
return 0;
}
//二分可能的长度
int l=1,r=n,mid;
while(l <= r){
mid= l+r >>1; //如果长度为 mid 的子串和满足>=m
if(check(mid)) r=mid-1;
else l= mid + 1;
}
//如果找不到这样的串，输出0
//if(l==n+1) cout<<0;
//else cout<<l; //输出左边界
cout<<l;//输出左边界
return 0;
}