• 周五. 8月 19th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

洛谷 P4025 [PA2014]Bohater(贪心)

admin

11月 28, 2021

传送门


解题思路

很妙的一道贪心题。
首先很显然的是,一定先把能回血的怪先干掉,然后再去干扣血的怪。
分类讨论:

  • 对于回血的怪,显然按照d从小到大排序,以免你一开始就被干死。
  • 对于扣血的怪,我们倒着考虑,从终止状态,每次减去a,然后加上d,就变成了回血怪的情况。
    所以对于扣血的怪按照a从大到小排序。

注意一定要开longlong并且特判是否全为扣血(或回血)的怪,不然总会有卡你的点。
image

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
struct node{
	int x,y,t,id;
}a[maxn];
int n;
long long k;
bool cmp(node a,node b){
	return a.t>b.t;
}
bool cmp2(node a,node b){
	return a.y<b.y;
} 
bool cmp3(node a,node b){
	return a.x>b.x;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].y>>a[i].x;
		a[i].id=i;
		a[i].t=a[i].x-a[i].y;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(a[i].t<0){
			sort(a+1,a+i,cmp2);
			sort(a+i,a+n+1,cmp3);
			break;
		}
		if(i==n) sort(a+1,a+n+1,cmp2);
	}
	for(int i=1;i<=n;i++){
		if(k<=a[i].y) {
			cout<<"NIE"<<endl;
			return 0;
		}
		k+=a[i].t;
	}
	cout<<"TAK"<<endl;
	for(int i=1;i<=n;i++) cout<<a[i].id<<endl;
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。