题解 P3619 魔法

· · 题解

题目传送>>P3619

题意简述：

题目分析：

根据题意，我们必须不断探索选择当下应该完成哪个任务致使最终能全部完成，这完全符合贪心算法，即局部最优导致产生全局最优解。判断贪心算法适用后，我们便需要选择贪心策略。根据题意，只有在 T>t_i 的前提下我们才能完成当下任务，而在完成第 i 个任务后我们的 T 可以获得改变，即 T+b_i。所以一般我们会想到先完成 b_i 大的任务，让 T 尽可能大，使其增得快减得慢，那么我们就可以大胆放心地持续推进完成所有任务。好，我们顺利得到贪心策略，立刻代码实现！可是事实真的是这样吗？在竞赛中，我们直接获得正确算法然后秒掉该题当然是幸事，但是我们在得到一个算法策略的时候并不应该直接敲代码，我们还要做什么呢？当然是验证算法策略是否正确，如果不正确那么你一来就敲的代码完全是竹篮打水一场空。
关于该题，我们对先前得到的优先选择 b_i 大的任务完成得贪心策略需要先进行验证。注意题面样例和数据范围我们都可得知 b_i 的值能是负的，而就是在 b_i 为负时，如果我们先选择了一个 b_i 值大一点的任务，我们在完成该任务后 T 便会加 b_i，即减小，可是当 T 得到上一个的改变，之后的任务的 t_i 大于或等于此时的 T，那么我们就不能接着完成接下来的任务了，可是万一前一个的 b_i 更小，我们的 T 被减小的幅度会变大，而第二个的 t_i 小，即“门槛”低，我们却是可以完成的。由此即可证明我们先前得到的贪心策略是错误的。
接下来我们推导正确的贪心策略，借助之前对旧策略的推翻过程，我们对其进行分析，如果我们先完成前一个任务致使 T 变小至达不到后二个任务的“门槛”，而先完成后一个任务，T 改变后我们依旧能达到前一个任务的“门槛”，此时：

T+b_1\le t_2 T+b_2>t_2

推得：

t_1-b_2<T\le t_2-b_1 t_1-b_2<t_2-b_1

即：

t_1+b_1<t_2+b_2

所以，我们只需依据 t_i+b_i 进行降序排序，再不断推进，一路到底即能完成所有任务，如有中断即失败。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define endl '\n'   //加速endl换行
struct task{    //利用结构体存ti,bi
    int t,b;
} a[100001];
int cmp(task x,task y)   //写cmp函数辅助sort排序   
{
    return x.t+x.b>y.t+y.b;
}
int main()
{
    //freopen("input.in","r",stdin);
    //freopen("print.out","w",stdout);
    ios::sync_with_stdio(0);   //加速cin输入和cout输出
    int Z,n,T;   //定义测试点数,任务数,拥有时间
    bool flag;   //定义flag标记任务推进进程
    cin>>Z;
    for (int i=1;i<=Z;i++)
    {
        cin>>n>>T;
        for (int j=1;j<=n;j++)
        {
            cin>>a[j].t>>a[j].b;
        }
        sort(a+1,a+1+n,cmp);   //排序
        flag=1;   //初始化flag
        for (int j=1;j<=n;j++)
        {
            if (T>a[j].t&&T+a[j].b>0)   //能够推进
            {
                T+=a[j].b;   //T改变
            }
            else
            {
                cout<<"-1s"<<endl;   //推进中断，直接输出不能完成，并换行
                flag=0;   //改变flag，标记为中断
                break;
            }
        }
        if (flag==1)   //任务得以一路到底
        {
            cout<<"+1s"<<endl;   //能输出够完成任务，并换行
        }
    }
    return 0;   //结束整个程序
}

结果（未吸氧）:


企鹅的题解到此结束，祝各位 OIers 进步 ++~