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

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

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

题目链接：A. The Contest
思路：

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

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

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

代码：

include

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;