问题标题: 酷町堂:4522 吃金币

0
0
已解决
汪恺恒
汪恺恒
中级启示者
中级启示者

题目描述 Description

在卡丁车赛道中间,每隔1m都有含有一定数量金币的金币堆。现在小P驾驶的卡丁车需要完成连续吃掉金币(不能掉头,只能往前行驶),且吃掉的金币总数要达到m的任务。请你帮小P设计一种方案,使小P在驾驶卡丁车连续吃掉达到m个金币的最小行驶长度。

输入描述 Input Description

两行,第一行两个数,n表示赛道上共有多少堆金币,m完成任务最少需要的金币数量
第二行,n个数,表示赛道的起点到终点的金币分布(相邻两数之间用空格隔开)

输出描述 Output Description

一个数,表示小P最小的行驶长度。

WA30

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
int n,m,a[1000005],sum,cnt,ans=0x3f3f3f3f;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        if(sum+a[i]>m){
            sum=a[i];
            ans=min(ans,cnt);
            cnt=1;
        }
        else{
            sum+=a[i];
            cnt++;
        }
    }
    cout<<ans;
    return 0;
} 

 


0
已采纳
周琪岳
周琪岳
资深光能
资深光能

写个二分查找试试

周琪岳在2021-01-10 19:17:24追加了内容

不对,是分治

我要回答