P3619 魔法

· · 题解

对于这个题，我刚开始的想法是，先把加时间的魔法全做完，再把减时间的魔法做完，但是按什么顺序呢？

我草率的按减时间从小到大去做，后经证实显然是不对的。。。 比如说这组数据： 1 3 100 27 -19 91 -39 42 -5 就卡掉了我。

后经高人指点，知道了要按t+b从大到小排序，但是为什么呢？

我也希望有大佬给证一下。。。。

不过没关系，蒟蒻可以自己脑补脑补，首先，T越大，我们就越有可能完成任务。 所以，我们每做一个魔法，就要想着给后面留更多时间，我个人觉得 t+b大的魔法，要么是加的时间比较多，要么就是需要比较大的t，所以需要先做掉。。。

qwq 

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=300000;
int T,n,z;
struct Things
{
    int t,b;
};
Things Th[Maxn];
inline int read()
{
    int fl=1,rt=0; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') fl=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){rt=rt*10+ch-'0';ch=getchar();}
    return fl*rt;
}
inline bool cmp(Things x,Things y)
{
    return x.t+x.b>y.t+y.b; 
}
inline void Greedy()
{
    int now=1,si=0;
    while(T>Th[now].t)
    {
        T+=Th[now].b; now++;
        if(now>n&&T>0){si=1; break;}
    }
    (si)?printf("+1s\n"):printf("-1s\n");
}
void read_ini()
{
    z=read(); 
    while(z--)
    {
        n=read(); T=read(); 
        for(int i=1;i<=n;i++) Th[i].t=read(),Th[i].b=read();
        sort(Th+1,Th+1+n,cmp);
        Greedy();
    }
}
int main()
{
    read_ini();
    return 0;
}
/*
1
3 100 
27 -19
91 -39 
42 -5

*/

嗯，先把加时间的都做掉，后面的按t+b递减排肯定也可以。。。