牛客寒假算法基础集训营2：处女座的期末复习（贪心入门）

103 阅读 0 评论 68 点赞

我是靠谱客的博主飞快小蜜蜂，最近开发中收集的这篇文章主要介绍牛客寒假算法基础集训营2：处女座的期末复习（贪心入门），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://ac.nowcoder.com/acm/contest/327/J
来源：牛客网

题目描述

**
快要期末考试了，处女座现在有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门课
备注:
考试时不能复习，保证考试时间不会重叠。

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

个人理解

起初一直想不懂这个贪心本人也是小白一个
题解的是先复习：还没有复习但是最先考试的科目
我起初想了一个下午一直没弄明白为什么最后先要sum+=2 到现在依旧只是稍微理解了一下我的思路是：先根据sort排把优先考试的放在前面然后判断你目前复习所用的时间是否超过了当前要考试的开始时间如果超过了就不能复习完了反之，先分时间段比如2 4 6 我的理解在于下一堂考试前必须考完前一堂所以后面sum+=2 其实我另一个想法是把第一堂复习了就直接考了但是这种情况总感觉不对还是上面那种解释合理点

源代码：

  	#include<bits/stdc++.h>
    #include<iostream>
    #include<cmath>
    #include<algorithm>
    #include<functional>
    using namespace std;
    
    typedef long long ll;
    struct st
    {
        int a,b;
    }a[100008];
    int n;
    bool cmp(st a,st b)
    {
        return a.b<b.b;
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].a);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].b);
        }
        sort(a+1,a+1+n,cmp);
        ll sum=0;
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            sum+=a[i].a;
            if(sum>a[i].b)
            {
                flag=0;
            }
            sum+=2;
    
        }
        if(flag)
        {
            printf("YESn");
        }
        else
        {
            printf("NOn");
        }
        return 0;
    }