题解 BZOJ 3709 [PA2014]Bohater

题解:

若d[x]<a[x],杀这个怪是有收益的,可以按d值从小到大杀。

若d[x]>a[x],考虑反过来的过程,如果都杀完后血量是S,那么从后向前就是 S-a[i]+d[i],相当于第一种情况,需要按a值从大到小杀。

分两部分排序模拟即可。

code:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
//by zrt
//problem:
using namespace std;
int n;long long z;
struct N{
int a,b,id;
}a[100005],b[100005];
int ca,cb;
inline bool cmp(N a,N b){
return a.a<b.a;
}
inline bool cmp2(N a,N b){
return a.b>b.b;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
scanf("%d%lld",&n,&z);
for(int i=1,x,y;i<=n;i++){
scanf("%d%d",&x,&y);
if(x<y){
a[ca].a=x;a[ca].b=y;a[ca].id=i;
ca++;
}else{
b[cb].a=x;b[cb].b=y;b[cb].id=i;
cb++;
}
}
sort(a,a+ca,cmp);
sort(b,b+cb,cmp2);
bool ok=1;
for(int i=0;i<ca;i++){
if(z<=a[i].a){
ok=0;break;
}else{
z+=a[i].b-a[i].a;
}
}
if(ok)
for(int i=0;i<cb;i++){
if(z<=b[i].a){
ok=0;break;
}else{
z+=b[i].b-b[i].a;
}
}
if(ok){
puts("TAK");
for(int i=0;i<ca;i++){
printf("%d ",a[i].id);
}
for(int i=0;i<cb;i++){
printf("%d ",b[i].id);
}
}else{
puts("NIE");
}
return 0;
}
评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框