题解归档 - cf813A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf813A
• 本地来源：problems/cf813A/idea.md
• 题目链接：https://codeforces.com/contest/813/problem/A
• 原始标题：cf813A — The Contest

思路

cf813A — The Contest

题意

按顺序做题，每题耗时 a_i，只能在一个或多个不重叠的开放区间 [l_j, r_j] 内提交（可一次提交多题）。求全部提交完成的最小时刻，不可能则 -1。

做法

multiset 存剩余耗时。对每个区间 [l, r]：

1. 若 cur < l：优先做能在 l 前做完的大题，否则做最小题（利用关站间隙做题）。
2. cur = max(cur, l) 后，在区间内贪心做「能塞进剩余窗口时间的最大题」并视为当场提交。
3. 区间结束后若还有题，累加做完；最终检查 cur 是否落在某个 [l, r] 内。

结论

Educational R22 A，贪心 + multiset。样例与边界（m=0、单题恰好在区间端点）手测通过。

代码

来源：problems/cf813A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:44:45
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1005;
ll l[maxn],r[maxn],n,m,i,j,k,cur,pd,ans;
multiset<ll>ms;
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>pd;
        ms.insert(pd);
    }
    cin>>m;
    for(i=1;i<=m;i++) cin>>l[i]>>r[i];
    cur=0;
    for(i=1;i<=m;i++){
        while(!ms.empty() and cur<l[i]){
            auto it=prev(ms.end());
            if(cur+*it<=l[i]){
                cur+=*it;
                ms.erase(it);
            }else{
                it=ms.begin();
                cur+=*it;
                ms.erase(it);
            }
        }
        cur=max(cur,l[i]);
        while(!ms.empty()){
            auto it=ms.upper_bound(r[i]-cur);
            if(it==ms.begin()) break;
            --it;
            cur+=*it;
            ms.erase(it);
        }
    }
    while(!ms.empty()){
        auto it=ms.begin();
        cur+=*it;
        ms.erase(it);
    }
    pd=0;
    for(i=1;i<=m;i++){
        if(l[i]<=cur and cur<=r[i]) pd=1;
    }
    if(pd) cout<<cur<<"\n";
    else cout<<-1<<"\n";
    return 0;
}