题解 P3619 【魔法】

· · 题解

这题虽然是一道绿题，但代码难度并不大，只要好好地想一下就可以了。

先说一下贪心思路

根据常识，我们可以知道，一定要先做bi>0的任务，否则就会使T越来越小，导致其它的都做不了

做完了bi>0之后，就要做bi<0的任务了，若bi<0,就按照

x.bi+x.ti>y.bi+y.ti

排序就可以了

下面上代码

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
template<class code>inline code read(const code &a)
{
    code x=0;short w=0;char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return w?-x:x;
}
int t,n,T;
bool flag;
struct node
{
    int ti,bi;
}a[100005]; 
bool cmp(node x,node y)
{
    if(x.bi>0||y.bi>0)//特别注意这里只要有一个bi>0就可以了（为此我卡了好几天） 
    {
        return x.ti<y.ti;//按照ti从小到大排序 
    }
    else 
    {
        return x.bi+x.ti>y.bi+y.ti;//否则就按照贪心策略中所说的排序 
    }
}
int main(){
    t=read(t);
    while(t--)//多组数据 
    {
        flag=0;//判断是否可以完成，注意每次循环都要重置 
        n=read(n),T=read(T);//读入 
        for(register int i=1;i<=n;++i)
        {
            a[i].ti=read(a[i].ti),a[i].bi=read(a[i].bi);
        }//读入 
        sort(a+1,a+n+1,cmp);//排序 
        for(register int i=1;i<=n;++i)
        {
            if(T>a[i].ti)
            {
                T+=a[i].bi;
            }//如果目前T够做，即T>a.ti，就把这项任务给做了 
            else //否则就表明不够做，跳出循环不做 
            {
                flag=1;
                break;
            }
            if(T<=0)//如果做完之后T<0了，就不符合题意，跳出循环不做 
            {
                flag=1;
                break;
            }
        }
        if(!flag)//如果可以做，就输出"+1s" 
        {
            printf("+1s\n");
        }
        else//如果不可以做，就输出"-1s" 
        {
            printf("-1s\n");
        }
    }
    return 0;//完美结束 
}