【最坏贪心】代码源每日一题div1 排列 2023.02.03

短命女 2024-03-27 13:01 54阅读 0赞

[排列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

**今天牛牛完结撒花辣！但是我还没补完题，感觉这几场rk都差不多，但是总体来说感觉签到签的有点困难，然后好不容易开到算法题，算法的题也最多只能出一题**

**然后后面这几天除了vpCF，牛牛补题，洛谷官方题单和代码源应该就不写了，课内的东西完全没学，感觉开学考要挂科了**

**今天这题感觉很简单，难度大约是签到题。但是我好像不太会，看dls讲解才写出来的，该家训了！**

**今晚就不vp了，因为有div4，直接打！**

题意：

![54f0094c85262a028f7785f7658941f9.png][]

思路：

感觉这道题涉及到两种贪心

一种就是普通的贪心，另一种就是最坏情况的贪心

题目说，是否**存在**一种排列，使得**任意**地安排b\[i\]给a\[i\]，都满足数列不增

这里的存在和任意有点耐人寻味

对于存在，我们考虑的排列一定是尽可能递减的

用反证法：如果排列递增，那么考虑把所有的b\[i\]（除了自身的b\[i\]）都加上a\[i\]上去，一定也是存在递增，这样就不满足任意性了（这个就是最坏情况的贪心）

所以我们直接把数组sort一下，然后去最坏情况的check就行了

这里的sort有个细节，就是如果a\[i\]相等，就把b\[i\]放到最后，这个属于是最坏情况的贪心，因为这样子加上的b\[i\]就会尽可能多，情况也就尽可能坏

check就是像上面写的那样，把所有的b\[i\]（除了自身的b\[i\]）都加上a\[i\]上去，看存不存在递增

Code：**换码风了，感觉火车头真的帅**

#include <bits/stdc++.h>
    #define int long long
    #define Please_ac return 0 
    #define y1 Y1
    #define LL long long
    #define PII pair<int,int>
    #define PDD pair<double,double>
    const int mxn=2e6+10;
    const int mod=1e9+7;
    const int Mnf=1e18;
    const int Inf=-1e18;
    const double eps=1e-8;
    const double e=exp(1.0);
    const double Pi=acos(-1.0);
    using namespace std;
    int sgn(double x){if(fabs(x)<eps) return 0;else return x<0?-1:1;}
    int dcmp(double x,double y){if(fabs(x-y)<eps) return 0;else return x<y?-1:1;}
    int ksm(int a,int b,int mod){int res=1;while(b>0){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
    
    struct ty{
        int a,b;
    }p[mxn];
    bool cmp(ty x,ty y){
        if(x.a==y.a) return x.b<y.b;
        return x.a>y.a;
    }
    int n,sum=0;
    void solve(){
        sum=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>p[i].a>>p[i].b;
            sum+=p[i].b;
        }
        if(n==2){
            cout<<"Yes"<<'\n';
            return;
        }
        sort(p+1,p+1+n,cmp);
        int ok=1;
        for(int i=2;i<=n;i++){
            if(p[i].a+sum-p[i].b>p[i-1].a) ok=0;
        }
        if(ok) cout<<"Yes"<<'\n';
        else cout<<"No"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();Please_ac;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/746
[54f0094c85262a028f7785f7658941f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/18c934d8860c4ae6bc489292c54da047.png