补充

CSDN 阅读体验更佳：【训练题34：贪心排序】G：模仿游戏 | 2021牛客寒假算法基础集训营5

题意

• 有 个怪兽，每个怪兽有出现时间 和类型
  有一位男生(泽鸽鸽)和一位女生(叶妹妹)玩游戏，每个人都可以每分钟打败一只怪。
  但是女生只有在男生之前打败 类型的怪物之后，才能去打败 类型的怪物。
  问你最优分配打败所有怪的最短时间

  范围

• 样例组数
  
  

  【思路：第一步】赛内思路 + 赛后过的

• 首先最明显的，每种类型的第一只怪都要男生去打败。
  那么最难的问题就是：同时有多种怪都是男生没打败过 (也就是女生无法先打)，男生要先选择打败哪个？
  凭直觉，哪种怪出现的越多就先打败哪种怪，这样女生才能去帮忙，不然只能光看着。
  经过思考之后，先打怪物出现多的或者后续出现多的，不一定是最优解。
  我们考虑的是让女生尽量每秒都能打败怪物 (女生得多强)
  也就是说，如果男生第一次打败了 类型的怪物，女生在什么时候开始就能自己打败 类型的怪了？

  【思路：第二步】

• 我们记录 表示类型为 怪物的第一次出现时间和第二次出现时间。
  我们记录 表示类型为 的怪物还没有打败过，攒了多少数量了。
  我们记录 表示目前位置女生可以打的怪物的数量。
  我们优先选择的策略如下：
  （1）首先女生先打。可以在 里面打一个怪物，，前提是有怪可打。
  （2）男生要优先打第一次出现的怪物。这些怪物的第二次出现时间最早的优先。
  （3）如果男生打败了第一次出现的怪物类型 ，那么之前所有的 类型的怪物女生都能打败了。也就是 转移到了 里去。
  （4）如果目前所有的怪物都不是第一次出现，那男生也在 里面打一个怪物。
  这样，代码就出来了：

  代码

• 时间复杂度：
  

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e5+50;
const int INF = 0x3f3f3f3f;

vector<int>V[MAX];
struct node{
    int p;
    int v;
    bool operator <(const node & ND)const{
        if(p != ND.p)return p > ND.p;
        return v < ND.v;
    }
};
priority_queue<node>Q1;
bool can[MAX];
int fir[MAX];
int sec[MAX];
int shu[MAX];
int duo;
int last;
int ans;
bool gan(){
    if(Q1.empty() && duo == 0)return true;
    ans++;
    if(duo)duo--;

    if(!Q1.empty()){
        can[Q1.top().v] = 1;
        duo += shu[Q1.top().v];
        Q1.pop();
    }else if(duo)duo--;

    return false;
}

int main()
{
    int T;scanf("%d",&T);
    while(T--){
        duo = 0;last = 0;ans = 0;

        int n;scanf("%d",&n);
        for(int i = 1;i <= 100000;++i){
            fir[i] = INF;
            sec[i] = INF;
            shu[i] = 0;
            can[i] = false;
            V[i].clear();
        }
        for(int i = 1;i <= n;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            last = max(last,a);
            V[a].push_back(b);
            if(a == fir[b]){
                fir[b] = sec[b] = a;
            }else if(a < fir[b]){
                sec[b] = fir[b];
                fir[b] = a;
            }else if(a < sec[b]){
                sec[b] = a;
            }
        }
        for(int i = 1;i <= last;++i){
            for(auto it : V[i]){
                if(i == fir[it]){
                    Q1.push({sec[it],it});
                    fir[it] = 0;
                }else if(can[it]){
                    duo++;
                }else {
                    shu[it]++;
                }
            }

            gan();
        }
        ans = last;
        while(!gan()){;}
        printf("%d\n",ans);
    }
    return 0;
}