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

87 阅读 0 评论 58 点赞

我是靠谱客的博主等待帆布鞋，这篇文章主要介绍处女座的期末复习（贪心），现在分享给大家，希望可以做个参考。

题目链接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

输出描述:

复制代码

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

示例1

输入

复制代码

输出

复制代码

1
YES

说明

复制代码

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

备注:

复制代码

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

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}