（贪心+区间排序）CodeForces 813A-The Contest

以你之姓@ 2022-05-16 10:19 168阅读 0赞

*  # （贪心+区间排序）CodeForces 813A-The Contest #

--------------------

*  ## 题目链接：[A. The Contest][] ##
 *  ## 思路： ##

给n道题及n道题每道完成需要的时间，和m个区间，题目只能在区间内提交，一次性提交题目不限制数目，求最短交完所有题目的时间

**首先，题目全部完成所需时间是恒定的，所以只需计算出题目完成总时间，然后在区间中找一个最短的时间点把题目全部提交就好**

***区间用结构体表示，然后进行排序，按左区间升序排，左区间相同则按右区间升序***

*  ## 代码： ##

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAX_SIZE 1005
    struct Period{
        int Begin;
        int End;
    };
    bool Mycmp(Period a,Period b)   //区间自定排序
    {
        if(a.Begin==b.Begin)
            return a.End<b.End;
        else
            return a.Begin<b.Begin;
    }
    
    Period Time_List[MAX_SIZE];
    int main()
    {
        int n,m;
        int Solve_Time=0;
        int One_Time;
        int Ans=-1;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>One_Time;
            Solve_Time+=One_Time;   //计算做题总时间
        }
        cin>>m;
        for(int i=0;i<m;i++)
            cin>>Time_List[i].Begin>>Time_List[i].End;
        sort(Time_List,Time_List+m,Mycmp);
        for(int i=0;i<m;i++)        //遍历区间
        {
            if(Time_List[i].Begin>=Solve_Time)    //开始时间大，在区间头把题目全部提交
            {
                Ans=Time_List[i].Begin;
                break;
            }
            if(Time_List[i].End>=Solve_Time) //做题总时间在区间中
            {
                Ans=Solve_Time;        //做完题马上提交
                break;
            }
        }
        cout<<Ans<<endl;
        return 0;
    }

[A. The Contest]: http://codeforces.com/problemset/problem/813/A