NOIP 模拟 $17\; \rm 时间机器$

题解 $by\;zj\varphi$

一道贪心的题目

我们先将节点和电阻按左边界排序，相同的按右边界排序

对于每一个节点，我们发现，选取左边界小于等于它的电阻中右边界大于它且最接近的它的一定是最优的

因为对于一个节点，其往后的节点中右边界可能会变大，要留出大的给后面的，换句话说，要让一个电阻发挥它最大的作用

注意：因为给出的电阻可能会有参数一样的，所以要用 $\rm multiset$

Code

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++

    template<typename T>inline void read(T &x) {

        ri f=1;x=0;register char ch=gc();

        while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

        x=f?x:-x;

    }

}

using IO::read;

namespace nanfeng{

    #define FI FILE *IN

    #define FO FILE *OUT

    template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}

    template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}

    typedef long long ll;

    static const int N=5e4+7;

    int T,n,m,fg;

    ll sum1,sum2;

    struct node{int l,h,nm;}U[N],R[N];

    inline int operator<(const node &n1,const node &n2) {return n1.h<n2.h;}

    inline int cmp(const node &n1,const node &n2) {return n1.l!=n2.l?n1.l<n2.l:n1<n2;}

    multiset<node> st;

    multiset<node>::iterator it;

    inline int main() {

        // FI=freopen("nanfeng.in","r",stdin);

        // FO=freopen("nanfeng.out","w",stdout);

        read(T);

        for (ri z(1);z<=T;p(z)) {

            st.clear();

            read(n),read(m);

            fg=sum1=sum2=0;

            for (ri i(1);i<=n;p(i)) {

                read(U[i].l),read(U[i].h),read(U[i].nm);

                sum1+=U[i].nm;

            }

            for (ri i(1);i<=m;p(i)) {

                read(R[i].l),read(R[i].h),read(R[i].nm);

                sum2+=R[i].nm;

            }

            if (sum2<sum1) {puts("No");continue;}

            sort(U+1,U+n+1,cmp);

            sort(R+1,R+m+1,cmp);

            ri lst=1;

            for (ri i(1);i<=n;p(i)) {

                while(lst<=m&&R[lst].l<=U[i].l) st.insert(R[lst]),p(lst);

                node tmp;

                while((it=st.lower_bound(U[i]))!=st.end()&&it->nm<=U[i].nm) {

                    U[i].nm-=it->nm;

                    st.erase(it);

                }

                if (it==st.end()&&U[i].nm) {fg=1;break;}

                if (U[i].nm)

                    tmp=*it,tmp.nm-=U[i].nm,st.erase(it),st.insert(tmp);

            }

            if (fg) puts("No");

            else puts("Yes");

        }

        return 0;

    }

}

int main() {return nanfeng::main();}

巴特西

NOIP 模拟 $17\; \rm 时间机器$

题解 \(by\;zj\varphi\)

最新文章

热门文章