问题标题: 重磅!全国多地刚刚发布!确定了!

0
0
已解决
李泽远
李泽远
高级天翼
高级天翼

https://newcourse.codingtang.com/#/problem/problemSub?id=1265

我就是个智障,连这一题都WA 10分,大佬帮忙看亿下:

#include<iostream>
using namespace std;
long long w,n,a[10005],cnt,sum;
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        if(i==n){
            if(sum==0){
                cnt++;
                break;
            }
            if(sum==a[i-1]){
                if(a[i]+sum<=w)
                    cnt++;
                else
                    cnt+=2;
                break;
            }
        }
        sum+=a[i];
        if(sum>w){
            cnt++;
            sum=a[i];
            continue;
        }
        if(sum==w){
            cnt++;
            sum=0;
            continue;
        }
        if(w-sum<a[i]){
            cnt++;
            sum=a[i];
        }
    }
    cout<<cnt;
    return 0;
}

 

李泽远在2020-08-17 14:13:46追加了内容

666


0
已采纳
赵逸凡
赵逸凡
初级启示者
初级启示者

目测是道贪心题。

你的思路很奇怪,这里推荐个贪心思路:

用maxn存当前组的总和,如果maxn比组允许的最大容量大,则说明这一组已经放不下这个元素了,就将组数加一

如果maxn比组允许的最大容量小,说明当前组还能放进这个元素,就放入,并且更新maxn

注:最终结果要加一

0
我要回答