0
已解决
新手天翼
4522 吃金币
经验值：1600
题目描述 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
不要蹭贴 要给思路
最后送大家一个鸭子
>(' )
)/
/(
/ `----/
\ ~=- /
高梓荣在2020-07-25 14:29:44追加了内容
忘说了
最好要用模拟
高梓荣在2020-07-25 14:41:08追加了内容
蹭贴者后果自负
0
已采纳
初级天翼
你管这叫模拟？
0
高级光能
5分题，我不会
0
中级启示者
我也不会
0
中级守护
虽说5分题，但是真的不难，其实就是卡丁车前进那么就把金币吃掉，这时可以拿个sum存储，当sum>=m,就可以再定义一个i，将前面的金币吐出，举个例子：
6个金币：3 1 7 5 4 6 当吃掉的金币总数要达到m：13，找最少
我们从1开始遍历
sum：3
sum：3+1=4
sum：3+1+7=11
sum：3+1+7+5=16
sum>=m
那么i从1开始
i：1 ai：3
那么将sum-ai
16-3=13
哎？是不是依然满足条件
i++
发现不满足了，
我们的cnt应该就知道这个数量了，当然后面依然要往后推，所以还要取一个最小值
重点代码：
sum+=a[j];
while(sum>=m)
{
mn=min(j-i+1,mn);
sum-=a[i++];
}
方晨顺在2020-07-25 21:51:23追加了内容
这里的cnt改成mn
