牛客寒假算法基础集训营2——J

101 阅读 0 评论 67 点赞

我是靠谱客的博主火星上老师，这篇文章主要介绍牛客寒假算法基础集训营2——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
2
YES

说明

复制代码

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

备注:

复制代码

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

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

思路：

看看此时前面的除去所占用的时间外，剩下的还够不够自己用

题解：

1，先按照考试时间从小到大排序（这样只用考虑此刻前面的已被占用的时间对自己的影响，后面不用管）

2，把此刻被占用的时间和考试时间比较就行了(结构体sort排序方法链接：链接 )

此刻的前面被占用的时间就是——此场考试需要复习的时间a[i]，加上前面所占的时间c[i-1]，再加上2

一定要用sort!!!我用冒泡就一直超时。唉，谁让我忘了可以用sort实现两个都变的排序呢！！！！

AC代码：

复制代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100007;
struct student{
    int a;
    int b;
}; 
int comp(const student &s1,const student &s2){//自己定义的排序规则 
    if(s1.b>s2.b)
	{
        return s1.b<s2.b;
    }
    else
	{
        return s1.b<s2.b;
    }
} 
int c[maxn]={0};//用来记录已被占用的时间 
int main()
{

	int n;
	scanf("%d",&n);
	struct student s[maxn];
	for(int i=0;i<n;i++)
	scanf("%d",&s[i].a);
	for(int i=0;i<n;i++)
	scanf("%d",&s[i].b);
	sort(s,s+n,comp);
	int answer=1;
	if(s[0].a<=s[0].b)
	{
		c[0]=s[0].a+2;
		for(int i=1;i<n;i++)
	{
		if(s[i].b>=s[i].a+c[i-1])
		{
			c[i]=c[i-1]+s[i].a+2;
		}	
		else
		{
			printf("NO");
			answer=0;
			break;
		}
	}
	if(answer==1)
	printf("YES"); 
	}
	else
	{
		printf("NO"); 
	}
	return 0;
 }