「土」巨石滚滚

「土」巨石滚滚

https://ac.nowcoder.com/acm/problem/53681

思路:
贪心
1.很容易想到如果一个障碍会增加稳定性,而一个会减少稳定性(最终结果),那么我们一定会先选择增加稳定性的,如果增加稳定性的都选不了那减少稳定性后就更选不了了。
2.都是增加稳定性时,先选择丧失稳定性最小的那个,这样处理后可以肯定,如果丧失稳定性最小的那个选不了,不管怎样选择它还是选不了。
3.都是减小稳定性时,先选择回馈稳定性最多的那个,比如:
2 40
30 34
40 50
我们肯定先选第二个再选第一个
Code:

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
struct node{
    int x,y,val;
    bool operator<(const node&a) const{
        if(val>0&&a.val>0) return x<a.x;
        if(val<0&&a.val<0) return y>a.y;
        return val>a.val;
    }
}q[500005];
int main() {
    js; int n,m,a,b,t;
    cin>>t;
    while(t--) {
        cin>>n>>m;
        for(int i=1;i<=n;++i) {
            cin>>q[i].x>>q[i].y;
            q[i].val=q[i].y-q[i].x;
        }
        sort(q+1,q+1+n); int flag=1;
        ll sum=m;
        for(int i=1;i<=n;++i) {
            if(q[i].x>sum) {
                cout<<"No\n",flag=0;
                break;
            }
            sum+=q[i].val;
        }
        if(flag) cout<<"Yes\n";
    }
    return 0;
}

为雨巨打call

全部评论
言简意赅,牛!
点赞 回复 分享
发布于 2021-07-12 14:35
大佬 你举得例子 按照你说的是不是应该123得选?
点赞 回复 分享
发布于 2020-06-12 18:21

相关推荐

烤点老白薯:他第二句话的潜台词是想让你帮他点个瑞幸或者喜茶啥的
mt对你说过最有启发的一...
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务