Jennie

一个贪心

首先应该贪心的处理掉所有的$b_i>0$的东西，但是对于$b_i<0$的怎么办呢

假设这里有$t_1,b_1,t_2,b_2$，并且只能先干1的话，那么有
$$
left{
begin{aligned}
T+b_1>t_2 \
T+b_2<t_1
end{aligned}
right.
$$
也就是有
$$
left{
begin{aligned}
T>t_2-b_1\
T<t_1-b_2
end{aligned}
right.
$$

所以有$t_2-b_1<t_1-b_2$所以说有$t_2+b_2<t_1+b_1$
也就是需要按照$t_i+b_i$从大到小排序即可

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int z;
int n,t;
int cnt1,cnt2;
struct ta{
    int a;
    int b;
};
ta q1[100101];
ta q2[100101];
int x,y;
bool cmp1(ta x,ta y){
    return x.a<y.a;
}
bool cmp2(ta x, ta y){
    return x.a+x.b>y.a+y.b;
}
int main(){
    scanf("%d",&z);
    while(z--){
        scanf("%d%d",&n,&t);
        cnt1=0;
        cnt2=0;
        for(int i=1;i<=n;++i){
            scanf("%d%d",&x,&y);
            if(y>0){
                q1[++cnt1].a=x;
                q1[cnt1].b=y; 
            } else{
                q2[++cnt2].a=x;
                q2[cnt2].b=y; 
            }
        }
        sort(q1+1,q1+cnt1+1,cmp1);
        sort(q2+1,q2+cnt2+1,cmp2);
        int f=0;
        for(int i=1;i<=cnt1;++i){
            if(t>q1[i].a){
                t+=q1[i].b;
            }else{
                f=1;
                break;
            }
        }
        for(int i=1;i<=cnt2;++i){
            if(f)
            break;
            if(t>q2[i].a){
                t+=q2[i].b;
                if(t<=0){
                    f=1;
                    break;
                }
            }else{
                f=1;
                break;
            }
        }
        if(!f)
        printf("+1sn");
        else{
            printf("-1sn");
        }
    }
    return 0;   
}