P3619 题解【魔法】

yezl · 2020-08-24 11:50:35 · 题解

这道题首先说实话有点氵（绿题呀同志们），不多说，先讲一下题意。

题目概述：

给你 Z 组测试点，以下输入 Z 个测试数据。
每组数据中输入 n 和总时间 T ，然后输入 n 个任务及其对应的 t_i 和 b_i ，当你完成一个任务时 T 就要加上 b_i （ b_i 可以是负数），且只有当此时 T 大于 t_i 时你才能完成这个任务。你可以选择任意顺序完成这些任务，如果可以完成输出 \texttt{+1s} 否则输出 \texttt{-1s} 。
（你还要保证任意时刻 T 都要大于 0 ）

思路分析：

这就是一道很水的排序加贪心题，那我们就要看得怎么排序了。
这样吧，我自己拟出两个很水的数据如下：

\text{样例1：1\qquad\qquad\qquad样例2：1} \qquad\quad\;\; 2\;\;3\qquad\qquad\qquad\qquad\;\,2\;\;\;5 \qquad\quad\;\; 4\;\;3\qquad\qquad\qquad\qquad\;\,3\;\;\text{-3} \qquad\quad\;\; 3\;\;2\qquad\qquad\qquad\qquad\;\,2\;\;\text{-1}

对于上面两个数据，很显然你按照 b_i 从大到小排序或者按照 t_i 从小到大排序都是不行的啦，这时候你会发现一个神奇的现象，如果按照 b_i+t_i 从大到小排序的话就可以非常 \mathcal{easy} 地解决，那这是为什么呢？

我们如果先做第一个任务会就会不能做第二个任务而先做第二个任务后却还能完成第一个任务，则我们可以得出：

也就是

就可得

即

得出结论了，那么直接开始写代码啦。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int z,T,n,flag=1;
struct node{
    int t,b;
}a[N];//记得要用结构体排序呀
inline int read()//快读，数据量大时比 scanf 还快点
{
    int num=0;//因为本题的特殊性，所以快读要负数啦
    char ch=getchar();
    if(ch=='-')//如果是负数
    {
        while(ch<'0'||ch>'9') ch=getchar();
        while(ch>='0' && ch<='9')
        {
            num=(num<<1)+(num<<3)+ch-'0';
            ch=getchar();
        }
        return -num;
    }
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0' && ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num;
}
bool cmp(node x,node y)//排序函数
{
    return (x.b+x.t)>(y.b+y.t);//按 b+t 从大到小排序
}
int main()
{
    z=read();//读入数据组数
    while(z--)
    {
        n=read(),T=read();//读入n，T
        for(int i=1;i<=n;i++)
            a[i].t=read(),a[i].b=read();
        sort(a+1,a+n+1,cmp);//排序
        for(int i=1;i<=n;i++)
        {
            if(T>a[i].t)//如果可以完成当前任务
                T+=a[i].b;//加上bi
            else//否则flag变成0
                flag=0;
            if(T<=0)//如果T<=0了（题目要求>0）
                break;//退出循环
        }
        if(T>0 && flag)//如果T>0并且flag变量不为0
            printf("+1s\n");//可以完成
        else//否则
            printf("-1s\n");//不可以完成
        flag=1;//flag变量记得还原o
    }
    return 0;
}

希望可以帮到大家。