CodeForces - 1203F1 Complete the Projects (easy version)(贪心)

72 阅读 0 评论 48 点赞

我是靠谱客的博主优秀花瓣，最近开发中收集的这篇文章主要介绍CodeForces - 1203F1 Complete the Projects (easy version)(贪心)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：点击查看

题目大意：现在有一个人，初始时有r元钱，现在有n个项目需要让他来解决，每个项目的门槛是a元钱，完成项目后的报酬是b元（报酬可以是负数），问能否在适当调整项目顺序后完成所有项目，能的话输出YES，否则输出NO

题目分析：我是在补题的时候做的这个题，所以就可以直接看到标签了，标签只写了是一个2100分的贪心，不过想了好久还只是想到了一点点部分，这个题目的核心是如何排序，只要排好序后，从头到尾按照题意扫描一遍就可以判断了

那么对于这个题目的排序，我们首先肯定是要优先拿报酬都是非负数的，这样才能让这个人的钱越来越多，则对于报酬都是正数的项目来说，最优解是让门槛较低的项目排在前面，这样就解决了报酬是正数的项目了

则剩下的就是报酬是负数的项目了，我们不能单纯对于门槛的大小来排序，随便找一组数据就hack掉了，比如：

2 10

10 -5

8 -1

所以肯定还是需要思考的，因为我们在完成项目后需要尽可能的让剩下的钱更多，那么就可以按照a+b作为权值进行降序排序，因为当这个人在完成当前项目的时候，钱一定是大于等于门槛的，我们不妨设当前的钱就是门槛，这样一来在完成当前项目后，剩下的钱就是a+b元了，这样就能简单证明出来了（好像不太严谨，但大概能说明这样排序的可行性了）

排完序之后扫一遍，按照规则判断就行了，规则就是这个人的钱每次必须都比门槛要高，并且钱不能出现负数

代码：

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
#include<unordered_map>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=110;

int n,r;

struct Node
{
	int a,b,flag;//flag=0:b为正或零 flag=1:b为负 
	bool operator<(const Node& k)const
	{
		if(flag!=k.flag)
			return flag<k.flag;
		if(flag==0)//都是正数
			return a<k.a;//这里如果都是正数的话，那么b的大小就无所谓了，只需要让a升序排列就行了
		else//都是负数 
		{
			if(a+b!=k.a+k.b)//优先按照a+b降序排序
				return a+b>k.a+k.b;
			return a>k.a;//其次按照a较大的排序
		}
	}
}a[N];

bool check()
{
	for(int i=1;i<=n;i++)
	{
		if(r<a[i].a)//如果当前的钱不足以抵消当前任务的门槛
			return false;
		r+=a[i].b;
		if(r<0)//如果中途出现了负数
			return false;
	}
	return true;
}

int main()
{
//  freopen("input.txt","r",stdin);
//    ios::sync_with_stdio(false);
    scanf("%d%d",&n,&r);
    for(int i=1;i<=n;i++)
    {
    	scanf("%d%d",&a[i].a,&a[i].b);
    	if(a[i].b>=0)
    		a[i].flag=0;
    	else
    		a[i].flag=1;
	}
    sort(a+1,a+1+n);
	if(check())
    	printf("YESn");
    else
    	printf("NOn");
    
    
     
     
     
     
      
     
    return 0;
}