[P7095 yLOI2020] 不离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

游戏中人物有两个属性，我们分别称之为「力量」和「精神」，同时哔哔有 n_n_ 件装备，穿戴第 i_i_ 件装备需要人物在穿戴前的力量值不低于 a_i，精神值不低于 b_i。在穿戴第 i 件装备后，人物的力量值会增加 c_i，精神值会增加 d_i。

哔哔可以自由选择穿装备的顺序，只要满足力量和精神不低于对应值，就可以穿戴该装备。

现在，咕咕想知道，如果想让哔哔穿戴上所有的装备，那么人物的初始力量值（即没有穿任何装备之前的力量值）最小应该是多少？在初始力量值最小的前提下，初始精神值（即没有穿任何装备之前的精神值）最小应该是多少？

显然，初始力量和初始精神都应该是非负整数。

分析：

第一遍排序过后，当在i这件武器时，如果starta+c[1,2,…,i-1]<a[i]，那么一定要更新starta，否则，加上c[i]，因此得到starta。对于nowa，如果a[i]<=nowa，那么将这几件武器按照cmp2扔进优先队列中，每次取出队首b小的武器，按照更新starta和nowa的方法更新startb，nowb。

代码如下：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;

const int N=1e5+10;
int t,n,starta,nowa,startb,nowb;
struct node{
    int a,b,c,d;
}arm[N];
struct cmp2{
    bool operator () (node a,node b){
        return a.b>b.b;
    }
};
priority_queue<node,vector<node>,cmp2>q;

inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int cmp1(node a,node b){
    return a.a==b.a?a.b<b.b:a.a<b.a;
}

int main(){
    t=read();n=read();
    for(int i=1;i<=n;i++){
        arm[i].a=read();arm[i].b=read();
        arm[i].c=read();arm[i].d=read();
    }
    sort(arm+1,arm+n+1,cmp1);
    for(int i=1;i<=n;i++){
        if(nowa<arm[i].a)starta+=(arm[i].a-nowa),nowa=arm[i].a;
        if(nowa<=1e9)nowa+=arm[i].c;
    }
    cout<<starta<<" ";
    nowa=starta;
    int aim=0;
    for(int i=1;i<=n;i++){
        while(arm[aim+1].a<=nowa&&aim<n)++aim,q.push(arm[aim]);
        node tmp=q.top();q.pop();
        if(nowb<tmp.b)startb+=(tmp.b-nowb),nowb=tmp.b;
        if(nowb<=1e9)nowb+=tmp.d;
        if(nowa<=1e9)nowa+=tmp.c;
    }
    cout<<startb;
    return 0;
}