首页 > 代码库 > [PA2014] [BZOJ 3709]~[BZOJ 3719] 合集

[PA2014] [BZOJ 3709]~[BZOJ 3719] 合集

2024-07-22 16:23:08   222人阅读

今天起尝试做套题喵~ （当然是因为被最大流的题目弄得恶心死了）

一共是 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] 合集


联系
我们