补充

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;
}