牛客 处女座的期末复习 (贪心)

拿到一看有点类似区间贪心, 其实更加简单, 首先我们对所有的考试按照开始时间升序排列, 我们优先复习最近要考试的科目
这里有一个小误区, 开始我也有点迷, 就是去维护了一个时间轴和时间指针, 结果仅仅是bool也导致了内存超限, 后来发现其实没有必要
我们在发现一个科目能够复习完之后, 直接在下一个科目的复习时间+2即可, 这一点的思维略微巧妙.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 1e5+10;
const LL maxa = 1e9+10;
 
struct node{
    int a, b;
}ab[maxn];
bool cmp(node a, node b) { return a.b < b.b;}
int n, ti = 0; //当前时间
int main()
{
 
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> ab[i].a;
    for(int i = 1; i <= n; i++)
        cin >> ab[i].b;
 
    sort(ab+1, ab+n+1, cmp); //考试时间升序排列
 
    bool flag = true;
    for(int i = 1; i <= n; i++){
        //优先复习完最近考试的
        if(ab[i].b-ti>=ab[i].a){ //考试前复习完
            ti += ab[i].a;
            ab[i+1].a += 2; //思维处, 直接在下一门课复习时间上加2
        }
        else { //考试前复习不完
            flag = false;
            break;
        }
    }
    if(flag) cout << "YES" << endl;
    else cout << "NO" << endl;
 
    return 0;
}

最后

以上就是微笑水壶为你收集整理的牛客 处女座的期末复习 (贪心)的全部内容，希望文章能够帮你解决牛客 处女座的期末复习 (贪心)所遇到的程序开发问题。

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