处女座的期末复习（贪心）

题目链接https://ac.nowcoder.com/acm/contest/327/J

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述 

快要期末考试了，处女座现在有n门课程需要考试，每一门课程需要花ai小时进行复习，考试的起始时间为bi，处女座为了考试可以不吃饭不睡觉，处女座想知道他能否复习完所有的科目（即在每一门考试之前复习完该科目）。每一门课的考试时间都为两小时。

输入描述:

第一行一个整数n

第二行n个整数a1,a2,…,an,表示每门课需要复习的时间

第三行n个整数b1,b2,…,bn,表示每门课考试的时间

1<=n<=105

0<=ai<=109

0<=bi<=109

输出描述:

如果处女座能复习完，输出”YES”，否则输出”NO”

示例1

输入

3
0 1 1
2 6 4

输出

YES

说明

在0-1小时复习第2门课，
在1-2小时复习第3门课，
在2-4小时考第1门课，
在4-6小时考第3门课，
在6-8小时考第2门课

备注:

考试时不能复习，保证考试时间不会重叠。

复习可以拆开，只要复习时间够了即可。

思路：先按考试开始时间排序，把每场考试之前所能用的复习时间求出来，到考试的时候再分配，如果分配完时间小于0，说明复习不完

#include<cstdio>
#include<algorithm>
using namespace std;
struct node {
	int a,b;
} p[100005];
bool cmp(node x,node y) {
	return x.b<y.b;
}
int  main() {
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&p[i].a);
	for(int i=1; i<=n; i++)
		scanf("%d",&p[i].b);
	sort(p+1,p+1+n,cmp);
	int sum=0;
	int l=0;
	bool flag=true;
	for(int i=1; i<=n; i++) {
		sum+=p[i].b-l;
		sum-=p[i].a;
		l=p[i].b+2;
		if(sum<0) {
			flag=false;
			break;
		}
	}
	if(flag) printf("YESn");
	else printf("NOn");
	return 0;
}

最后

以上就是等待帆布鞋为你收集整理的处女座的期末复习（贪心）的全部内容，希望文章能够帮你解决处女座的期末复习（贪心）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。