2020 kickstart E round C Toys(プライオリティキュー)

タイトル:
n個のtoyが1つの輪に並んでいて、各toyにはe[i],r[i],e[i]があり、e[i]の時間をかけてこのtoyを遊ぶ必要があり、r[i]はこのおもちゃが再び遊ぶことができるcd時間と理解でき、1人の子供は0番目のおもちゃから始まり、i+1個のおもちゃに順番に遊ぶたびに、1つのおもちゃが遊ばれる前提は、前回遊ばれた時間がr[i]を超えることである.游べないおもちゃに出会ったら、子供は止まって動かないで、さもなくばずっと游んでいます.どのくらいのtoyを削除すれば、子供が最も長く遊ぶことができ、最も長い時間を保証する場合、最も少ないおもちゃを削除することができます.
 
考え方:
第1ラウンドはきっとすべて游ぶことができて、肝心なのは第2ラウンドを见て、私达は1ラウンドのおもちゃを完成する时间をtimと覚えて、それでは1つのおもちゃが更に第2ラウンドの时游ぶことができるかどうかを判断するのは単tim-e[i]>=r[i]で、もし大きいならば游ぶことができて、小さいならばだめです.
そしてこの問題の最も簡単な考え方は実は第2ラウンドの時に私たちが游ぶことができないことに出会って除去して、順番に除去して、しかし1つの問題があって、除去した後にtimは更に小さくなって、またもっと多くのtoyが游ぶことができなくて、第3ラウンドの削除が必要で、第4ラウンドの削除.これでn^2のアルゴリズムになるので、きっとだめです.
そして注目すべきは、toyが削除される順序は重要ではありません.r[i]>tim-e[i]はそれぞれ削除しなければならないので、私たちが削除するときは遊びの順序で削除する必要はありません.t[i]>tim-e[i]を満たすtoyを直接見つけて削除すればいいので、順序を気にしないでください.そしてこの時、timが変化したとき、どのtoyがr[i]>tim-e[i]を満たすかを探します.しかし、このように直接探すのは難しいので、不等式を変換してr[i]+e[i]>sumの削除を探すことを考えることができます.これにより、r[i]+e[i]の優先キューを簡単に維持することができます.私たちは順番にtoyを遍歴し、toy更新timを削除するときは、優先キューに行ってtop()の値が新しいtimより大きいかどうかを見て、これで最大n回削除することができます.時間の複雑さはo(nlogn)で、最後に削除されなければ、無限の時間で遊ぶことができます.
 
コード:

#include 
#define ps push_back
using namespace std;
const long long inf=1e18;
const int maxn=1e5+5;
int n;
int e[maxn], r[maxn];
long long ans;
int num;
struct node
{
    int x;
    int id;
    bool operator >n;
    ans=0;
    priority_queueq;
    for(int i=0; itim)
        {
            tim-=e[i];
            cur_tim-=e[i];
            cnt++;
            while(!q.empty() && q.top().x>tim)
            {
                tmp=q.top();
                tim-=e[tmp.id];
                cur_tim-=2*e[tmp.id];
                q.pop();
                cnt++;
            }
        }
        else {
            q.push(tmp);
            cur_tim+=e[i];
        }
        if(cur_tim>max_tim)
        {
            num=cnt;
            max_tim=cur_tim;
        }
    }
    if(cnt!=n)
    {
        num=cnt;
        max_tim=inf;
    }
    if(max_tim!=inf)printf("%d %lld
", num, max_tim);
    else printf("%d INDEFINITELY
", num);
}
int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0);
    int t;
    cin>>t;
    for(int i=1; i<=t; i++){
        cout<