一道贪心, 填一年前的坑

懵逼的 题目

传送至 Bilibili

扯淡的 题解

好像很早以前(NOIp2017?)的时候学长就安利做这个来着…现在才发现推荐的三道题没一个是当时的可做题

数据范围显然是个贪心来着…

然后也显然要按照是否能够增加血量分别排序来着…

  • 能够增加血量的话, 毫无疑问是要按照cost来升序搞的…如果当前打不过, 之后的肯定也打不过, 不如先打掉当前的加点血再说…
  • 能减少血量的话就比较麻烦…写了三种排序(按照cost升序 / 降序, 按照减少血量的多少排序), 都被我自己hack掉了…(见注释里的数据), 于是我们要按照weight升序来排….

为什么呢…因为我们要TAK的话就一定要gank死所有的boss…所以所有的cost都一定会减掉的…然后就可以按照weight排了?

也许吧…

诶诶诶黄学长的解释很好啊 _(:з」∠)_

不管用什么顺序杀掉剩下的怪,最后体力last是确定的
倒序来看,相当于将血药吐出来然后返还杀怪的消耗,那么显然也是按照损失体力(即血药回血量)升序,正回来即是降序。。。
即分为两部分,杀完能回血的按照消耗升序,剩余按血药回血量降序,然后模拟一遍判断是否合法即可

沙茶的 代码

/**************************************************************
    Problem: 3709
    User: Cansult
    Language: C++
    Result: Accepted
    Time:2524 ms
    Memory:28640 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define LL long long
using namespace std;
struct boss
{
    LL weight, cost, bh;
    bool ifDev;
}a[MAXN];
int n;
bool cmp1(boss x, boss y)
{ return x.ifDev > y.ifDev; }
bool cmp2(boss x, boss y)
{ return x.cost < y.cost; }
bool cmp3(boss x, boss y)
{ return x.weight > y.weight; }
int main()
{
    LL fir, cnt1 = 0;
    scanf("%d%lld", &n, &fir);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &a[i].cost, &a[i].weight);
        a[i].bh = i;
        a[i].ifDev = (a[i].weight >= a[i].cost);
        cnt1 += a[i].ifDev;
    }
    sort(a + 1, a + n + 1, cmp1);
    sort(a + 1, a + cnt1 + 1, cmp2);
    sort(a + cnt1 + 1, a + n + 1, cmp3);
    for (int i = 1; i <= n; i++)
    {
        if (fir > a[i].cost)
            fir += a[i].weight - a[i].cost;
        else
        {
            puts("NIE");
            return 0;
        }
    }
    puts("TAK");
    for (int i = 1; i <= n; i++)
        printf("%lld ", a[i].bh);
    return 0;
}

// 如果我按照cost排序的话, 如果打过了当前的这个以后的都打不过了会发生什么?
// Emmmmm好像出锅了...

/*
3 5
3 1
4 8
8 3

2 10
8 0
2 1

2 10
9 2
2 0
*/

By 沙茶 Cansult