Description

有一天叶妹妹和泽鸽鸽他们一起参加一个模仿游戏，这个游戏主要任务是打怪兽，每个怪兽都有一个权值，如果两个怪兽的权值相同，那么表示这两个怪兽是同一类型的怪兽。对于任何一个怪兽，只能由一个人去打败它，并且一个人无法同时打两只及两只以上的怪兽。泽鸽鸽和叶妹妹打败任何一个怪兽都只需要花费一分钟，并且他们只能在整数分钟去打怪兽，不能出现小数分钟。由于这是模仿游戏，因此叶妹妹只能模仿泽鸽鸽去打败怪兽。比如，当泽鸽鸽在之前已经打败了权值为x 的怪兽后，叶妹妹才能去打权值为x 的怪兽（即相同类型的怪兽）。现在给出每个怪兽的出现时间和权值，请你设计一个最优的顺序使得所有怪兽都被打败后的时间最早！

Solution

因为答案是最早的时间,怪兽出现与时间有关,而且时间轴的大小也足够小,所以可以考虑遍历时间来找最大值.
关于贪心策略的话,最简单的是把第一次见到的都给泽鸽鸽打,其他的都给叶妹妹打.但是这样显然会wa,因为泽鸽鸽的时间并没有充分利用(被迫加班?).所以可以在遍历时间时,在该时间结束时去寻找此时的泽鸽鸽是不是在忙,如果没在打怪兽,那么就让他打怪兽,并且在叶妹妹的队列中的个数减一,也就是减一分钟.这样就能保证泽鸽鸽在有空的时候都能帮叶妹妹分担.于是就可以找出最优的时间就是max(泽鸽鸽终止的时间,叶妹妹终止的时间).

Code

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef long double ld;
#define endl '\n'
#define inf std::numeric_limits<ld>::max()
using namespace std;
#define Please return
#define AC 0
struct _IO
{
    _IO()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
    }
} _io;

inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

struct lzh{
    int t,a;
};

bool cmp(lzh a,lzh b){
    if(a.t==b.t){
        return a.a<b.a;
    }
    return a.t<b.t;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n;
        lzh a[n];
        for(int i=0;i<n;i++){
            cin>>a[i].t>>a[i].a;
        }
        vector<int> x[200001];
        int vis1=0,vis2=0;
        int vis[n+1];
        memset(vis,0,sizeof(vis));
        sort(a,a+n,cmp);
        for(int i=0;i<n;i++){
            x[a[i].t].push_back(a[i].a);
        }
        for(int i=1;i<=200000;i++){//开到2e5是为了保证数据不会溢出
            for(int j=0;j<x[i].size();j++){
                if(vis[x[i][j]]==0){
                    vis1=max(vis1+1,i);
                    vis[x[i][j]]=i;
                }
                else{
                    if(vis[x[i][j]]==i){
                        vis2=max(i+1,vis2+1);
                    }
                    else{
                        vis2=max(i,vis2+1);
                    }
                }
            }
            if(vis1<vis2&&vis1<i){
                vis1=i;
                vis2--;
            }
        }
        //cout<<vis1<<" "<<vis2<<endl;
        cout<<max(vis1,vis2)<<endl;
    }
    Please AC;
}