0
已解决
新手天翼
4522 吃金币经验值：1200 时间限制：1000毫秒
题目描述 Description
在卡丁车赛道中间，每隔1m都有含有一定数量金币的金币堆。现在小P驾驶的卡丁车需要完成连续吃掉金币（不能掉头，只能往前行驶），且吃掉的金币总数要达到m的任务。请你帮小P设计一种方案，使小P在驾驶卡丁车连续吃掉达到m个金币的最小行驶长度。
输入描述 Input Description
两行，第一行两个数，n表示赛道上共有多少堆金币，m完成任务最少需要的金币数量
第二行，n个数，表示赛道的起点到终点的金币分布（相邻两数之间用空格隔开）
输出描述 Output Description
一个数，表示小P最小的行驶长度。
样例输入 Sample Input
11 13
1 2 4 5 9 4 1 10 1 1 7
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
1<=n<=1,000,000
1<=m<=1000
1<=每堆金币数<=m
#include<iostream>
using namespace std;
int a[1010],k;
int maxn[1000005],b[1000005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
int cnt=0;
while(maxn[i]<m&&cnt<i){
cnt++;
maxn[i]+=a[cnt];
b[i]++;
}
}
for(int i=1;i<=n;i++){
if(k<maxn[i]){
k=b[i];
}
}
cout<<k;
return 0;
}样例都过不了。。。
0
已采纳
中级启示者
不想再打一遍，你自己看
0
新手启示者
和一定路程最短连续子序列！
0
新手启示者
明天告诉你
0
被禁言
修练者
窗口：用维护内部金币数量之和>=m的最小行驶长度
--------------------------------------------
先移动右指针r,直到窗口数量之和sum>=m的最小行驶长度
求窗口大小的最小值
再一步一步移动左指针l
*/
整型 n,m,sum,ans=0x3f3f3f3f,t;
整型 a[1000005];
开始(){
输入>>n>>m;
循环(int i=1;i<=n;i++){
输入>>a[i];
t+=a[i];
如果(a[i]==m){
输出<<1;
return 0;
}
}
如果(t<m) {
cout<<-1;
return 0;
}
整型 l=1,r=1;
while(r<=n){
while(sum<m&&r<=n){//移动右指针r
sum+=a[r];
r++;
}
如果(r>n) break;
ans=min(ans,r-l);
sum-=a[l];
l++;
}
输出<<ans;
return 0;
}
望采纳！！！
0
新手启示者
思路：
1、输入；
2、判断，a[i]<=n，n-=a[i]，cnt++，maxn=max（maxn,cnt）
3、cnt清零，n赋值为x（x初值为n)
4、输出
