列表

详情

NC200119. Monster Fighting

描述

In the Game World, we all know the common scene, if you want to make your heroes stronger, you need to defeat monsters and upgrade yourselves.
Little Gyro is also a computer game fan. In a computer game Monster Fighting, Little Gyro need to defeat against n monsters (numbered from 1 to n). Little Gyro's hero has an initial health m. In order to defeat the i-th monster, Little Gyro will lose a_i HP (Health Penalty), However, the monster will drop a blood bottle for Little Gyro to restore d_i HP. During the game of Monster Fighting, your health cannot be reduced to 0 or below.
Given the HP values a_i, d_i for each monster, Little Gyro wants to know whether there exists a certain order that Little Gyro can defeat all the monsters.

输入描述

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n, m (1 ≤ n, m ≤ ), indicating the number of the monsters and the initial health of Little Gyro's hero.
In the following n lines, each line contains two integers a_i, d_i (1 ≤ a_i, d_i ≤ ), indicating the HP values that Little Gyro lose and gain when fighting against the i-th monster.
It's guaranteed that the sum of n of all test cases will not exceed .

输出描述

For each test case, if Little Gyro can defeat all the monsters within a certain order, print "Yes" (without quotes), otherwise, print "No" (without quotes) instead.

示例1

输入: 

2
3 4
1 2
3 4
4 5
1 1
2 1

输出: 

Yes
No

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 87ms, 内存消耗: 2528K, 提交时间: 2020-03-23 00:42:41 

#include<iostream> 
#include<map>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct f{
	long long a;
	long long b;
};
static bool myCompare1( f& a1, f& a2)
{
    return a1.a < a2.a;
}
static bool myCompare2( f& a1, f& a2)
{
    return a1.b > a2.b;
}
int main(){
	int n;
	cin>>n;
	while(n--){
		long long a,hp;
		vector<f> t1;
		vector<f> t2;
		long long i=0,j=0,k=0;
		cin>>a>>hp;
		while(a--){
			f t;
			cin>>t.a>>t.b;
			if(t.b>=t.a)
				t1.push_back(t);
			else
				t2.push_back(t);
		}
		sort(t1.begin(),t1.end(),myCompare1);
		sort(t2.begin(),t2.end(),myCompare2);
		int flag=1;
		for(int i=0;i<t1.size();i++){
			if(t1[i].a<hp){
				hp=hp-t1[i].a+t1[i].b;
			}else{
				flag=0;
				break;
			}
		}
		for(int i=0;i<t2.size();i++){
			if(t2[i].a<hp){
				hp=hp-t2[i].a+t2[i].b;
			}else{
				flag=0;
				break;
			}
		}
		
		if(flag)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 42ms, 内存消耗: 2276K, 提交时间: 2019-12-08 11:29:06 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn=1e6+10;
int T,n,lena,lenb;
long long H;
struct da
{
	int x,y;
	bool operator <(const da &aa) const 
	{
		return x<aa.x;
	}
}a[maxn],b[maxn];
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%lld",&n,&H); lena=lenb=0;
		for (int i=1;i<=n;i++)
		{
			int aa,dd; scanf("%d%d",&aa,&dd);
			if (dd-aa>=0) a[++lena]={aa,dd-aa};
			else b[++lenb]={aa,dd-aa};
		}
		sort(a+1,a+lena+1); sort(b+1,b+lenb+1); bool ok=1;
		for (int i=1;i<=lena;i++) if (H>a[i].x) H+=a[i].y;else {ok=0; break;}
		for (int i=lenb;i>=1;i--) if (H>b[i].x) H+=b[i].y;else {ok=0; break;}
		printf(ok?"Yes\n":"No\n");
	}
return 0;
}
/*
1
3 6
4 3
5 10
10 5
*/

上一题

© 2024 nowcoder.com