题目描述
新冠疫情肆虐,不仅仅是学校,工厂,大家也都在为防疫贡献自己的力量。
小丁作为科丁市的卡车司机,也想为科丁城的防疫贡献绵薄之力。已知小丁的卡车最多能装C单位货物,现在有n个地点可以装防疫物资,n个地点拥有的物资数量依次为:A[1],A[2],A[3],......,A[n]。小丁可以任选一个地点p,然后从地点p开始,连续地收集物资,直到装满卡车为止!为了节省时间,小丁希望跑的地点越少越好!问小丁最少跑多少个地点可以完成物资收集。
输入格式
第一行:两个空格分隔的正整数c和n,分别表示小丁卡车的容量和地点数量。
第二行:由n个空格分隔的正整数,表示每个地点的防疫物资数量。
输出格式
输出只有一行:为小丁收集到足够物资最少需要跑的地点数量。
输入输出样列
输入样例1:
7 6
2 3 1 2 4 3
输出样例1:
2
输入样例2:
4 3
1 4 4
输出样例2:
1
说明
【输入输出样例 1 说明】
样例1说明:小科需要在6个位置中连续挑选若干个地点,使得装满7单位的物资。
可选择的方案是:{2,3,1,2}、{3,1,2,4}、{1,2,4}、{2,4,3}、{4,3}。
目标是选择的地点越少越好!选最后一种方案,此时只需要跑两个地点。
【数据规模与约定】
数据范围1 <= n <= 10^5,1 <= c <= 10^9,1 <= A[i] <=10^5;数据保证:A[1]+A[2]+......+A[n]>=c。
我的代码
#include<bits/stdc++.h>
using namespace std;
const int N=100005,INF=0x7fffffff;
int c,n,a[N],s[N];
int main(){
cin>>c>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int ans=n;
for(int i=1;i<=n;i++){
int l=i,r=n,t=INF,flag=2,pre=INF;
if(a[i]>=c)t=1;
else if(i<n&&(a[i]+a[i+1]>=c)){
t=2;
}
else if(i<n-1&&(a[i]+a[i+1]+a[i+2]>=c)){
t=3;
}
else{
while(l<r&&r<=n){
if(s[r]-s[l-1]>=c)
if(r-l+1<t){
t=r-l+1;
r-=((r-l+1)>>1);
}
else break;
else r+=((r-l+1)>>1);
}
}
if(s[r-1]-s[l-1]>=c)t=r-l;
if(s[n]-s[l-1]>=c)t=n-l+1;
if(t!=INF){
ans=min(ans,t);
}
}
cout<<ans;
return 0;
}
全WA,求为什么