水题笔记_ BZOJ3709 [PA2014]Bohater [贪心, 清奇脑回路]

一道贪心, 填一年前的坑

懵逼的 题目

传送至 Bilibili

扯淡的 题解

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

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

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

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

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

也许吧…

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

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

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**************************************************************
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