2J.处女座的期末复习（C++）

本文主要是介绍2J.处女座的期末复习（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

处女座的期末复习（C++）

点击做题网站链接

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

输入描述:
第一行一个整数n
第二行n个整数a1,a2,…,an,表示每门课需要复习的时间
第三行n个整数b1,b2,…,bn,表示每门课考试的时间
$1<=n<=10^5$
$0<=ai<=10^9$
$0<=bi<=10^9$

输出描述:
如果处女座能复习完，输出”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门课

备注:
考试时不能复习，保证考试时间不会重叠。
复习可以拆开，只要复习时间够了即可。

解题思路：
贪心算法，每次复习还没有复习但是最先考试的科目即可

解题代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;struct st
{int a;int b;
}course[N];bool cmp(st x, st y) { return x.b < y.b; }//对b[i]从小到大排序int main()
{int n;//考试课程数cin >> n;for(int i=0;i<n;++i) cin >> course[i].a;//每门课需要复习的时间for(int i=0;i<n;++i) cin >> course[i].b;//每门课考试的时间sort(course,course+n,cmp);//对b[i]从小到大排序long long int sum = 0;int i;for(i=0;i<n;++i){sum += course[i].a;if( sum > course[i].b ) break;sum += 2;//再加上考试的2小时}if( i==n ) cout << "YES" << endl;else cout << "NO" << endl;return 0;
}

笔记

关于sort()函数的补充结构体用法：

sort函数的时间复杂度为n*log2(n)，执行效率较高。
sort函数的形式为sort( first，end，method )，其中第三个参数可写可不写。
若为两个参数，则sort的排序默认是从小到大。
若为三个参数，则需要写一个“比较”函数，用于判断是从小到大排序还是从大到小排序。

#include <iostream>
#include <algorithm>
using namespace std;struct node 
{int a;//.........
};bool cmp(node x,node y)
{if(x.a != y.a) return (x.a > y.a);//对a从大到小排序
}int main()
{node t[5];for(int i=0;i<5;++i) cin >> t[i].a;sort(t,t+5,cmp);for(int i=0;i<5;++i) cout << t[i].a;cout << endl;
}