大佬们,这道题贪心为什么不能这么写?或者说可以贪心嘛?
查看原帖
大佬们,这道题贪心为什么不能这么写?或者说可以贪心嘛?
1217330
xdedb楼主2024/4/5 20:19

为什么贪心不能这么写呢,只有30分,自己看了一会看不出为什么

#include <iostream>
#include <algorithm>
using namespace std;
struct plane{
    int T,D,L;
};

bool cmp(plane a,plane b){
    if((a.T+a.D+a.L)==(b.T+b.D+b.L)){
        return (a.T+a.D)<(b.D+b.T);
    }else{
        return (a.T+a.D+a.L)<(b.T+b.D+b.L);
    }
}

int main(){
    int num;
    cin>>num;
    for(int i=0;i<num;i++){
        int n;
        cin>>n;
        plane tree[n];
        for(int t=0;t<n;t++){
            cin>>tree[t].T>>tree[t].D>>tree[t].L;
        }
        sort(tree,tree+n,cmp);
        int flag=1;
        int tmp=0;
        for(int t=0;t<n;t++){
            if(tmp>tree[t].D+tree[t].T){
                flag=0;
                break;
            }
            tmp=max(tmp+tree[t].L,tree[t].T+tree[t].L);
        }
        if(flag){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
}

给个hack数据也是很好的!谢谢大佬!

2024/4/5 20:19
加载中...