首页 > 代码库 > [PA2014] [BZOJ 3709]~[BZOJ 3719] 合集
[PA2014] [BZOJ 3709]~[BZOJ 3719] 合集
今天起尝试做套题喵~ (当然是因为被最大流的题目弄得恶心死了)
一共是 10 道题一道一道做 预计 3~4 内做完 尽情期待
[BZOJ 3709]Bohater
一眼就能感受到贪心的气息
因为很直观地,能加血的怪先打掉是不二法则
所以把怪分为两类: 能加血的和要掉血的
前者按伤害升序排序,算出最大血量
但后者要怎么搞让我很是郁闷~一开始是按伤害降序的,结果秒 WA 了
想想也是 Z=1000 怪1: a=998 d=1 怪2: a=100 d=99 你说先打哪只?
看来和回血量也是有关系的,事实上按回血量降序排序即可
但为什么呢?
因为最后血量是固定的,所以可以看成从最后血量开始,吐出血瓶,加上打怪时的血量一路逆推(此时怪的 d 是 a ,a 是 d) 问能否打败所有怪
然后就变成和前面一样的问题了
就这么 A 掉了,看来凡事都要反过来想想才行 (顺便提醒一句,此题 z 变量要开 long long)
#include <cstdio>#include <algorithm>const int sizeOfMonster=100025;inline int getint(){ register int num=0; register char ch; do ch=getchar(); while (ch<‘0‘ || ch>‘9‘); do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); return num;}inline void putint(int num){ char stack[15]; register int top=0; if (num==0) stack[top=1]=‘0‘; for ( ;num;num/=10) stack[++top]=num%10+‘0‘; for ( ;top;top--) putchar(stack[top]); putchar(‘ ‘);}struct node{ int id, d, a; inline node():id(0), d(0), a(0) {} inline node(int _id, int _d, int _a):id(_id), d(_d), a(_a) {}};int n; long long z;int t1, t2;node add[sizeOfMonster], sub[sizeOfMonster];inline bool cmpForAdd(node x, node y) {return x.d<y.d;}inline bool cmpForSub(node x, node y) {return x.a>y.a;}int main(){ register int i; n=getint(), z=getint(); for (i=1;i<=n;i++) { int d=getint(), a=getint(); if (d<=a) add[t1++]=node(i, d, a); else sub[t2++]=node(i, d, a); } std::sort(add, add+t1, cmpForAdd); for (i=0;i<t1;i++) { if (z<=add[i].d) break; z=z+add[i].a-add[i].d; } if (i<t1) {printf("NIE\n"); return 0;} std::sort(sub, sub+t2, cmpForSub); for (i=0;i<t2;i++) { if (z<=sub[i].d) break; z=z+sub[i].a-sub[i].d; } if (i<t2) {printf("NIE\n"); return 0;} printf("TAK\n"); for (i=0;i<t1;i++) putint(add[i].id); for (i=0;i<t2;i++) putint(sub[i].id); putchar(‘\n‘); return 0;}
[PA2014] [BZOJ 3709]~[BZOJ 3719] 合集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。