萌新悬关
查看原帖
萌新悬关
704275
无名之雾楼主2024/1/20 22:58

虽然我知道我的复杂度不对,但是我全WA了 求助 可能贪心策略不对,如果可以的话帮忙讲一下贪心策略,万分感谢

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
    int n,m;
    cin>>n>>m;
    int sum=0;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
    sort(a+1,a+n+1);
    int q=1;
    int ans=0;
    int mon=n;
    while(sum>0){
        if(a[q]%2==1){
            for(int i=q;i<=n;i++){
                a[i]-=1;
                if(a[i]==0)mon--,q=i+1;
                sum-=1;
            }
            ans+=mon;
        }
        if(a[q]%2==0){
            a[q]-=2;
            if(a[q]==0)mon--,q++;
            sum-=2;
            ans+=mon;
        }
    }
    cout<<ans;
    return 0;
}
2024/1/20 22:58
加载中...