【题解】Luogu p1181 【数列分段Section I】

算法:貪心

貪心策略很簡單,每次盡量選擇多的數,且使其和不大於m

但是實現嘛,這種好像得策略一般不好實現,下面就是一例

int main(){
    std::vector<int> A;
    int n,m;
    scanf("%d %d",&n,&m);

    int gg;
    for(int i = 0;i < n;i++){
        scanf("%d",&gg);
        A.push_back(gg);
    }

    int sum = 0,ans = 0;
    for(int i = 0;i < n;i++){
        if(A[i] + sum > m){
            sum = 0;
            ans++;
        }
        sum += A[i];
    }

    if(sum){
        ans++;
    }

    printf("%d",ans);

    return 0;
} 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注