求助
  • 板块学术版
  • 楼主ftzx
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/4/6 22:30
  • 上次更新2023/10/28 04:24:39
查看原帖
求助
614672
ftzx楼主2022/4/6 22:30
题目描述
新冠疫情肆虐,不仅仅是学校,工厂,大家也都在为防疫贡献自己的力量。

小丁作为科丁市的卡车司机,也想为科丁城的防疫贡献绵薄之力。已知小丁的卡车最多能装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,求为什么
2022/4/6 22:30
加载中...