2021秋季算法入门班第五章习题：优先队列、并查集

小A与任务

题面

需要完成n个任务，第i个任务需要 $x_{i}$ 的时间，必须在 $y_{i}$ 时间前完成，支付m枚金币可以在提前 $m * z_{i}$ 的时间完成。

思路

首先一定是按照完成时间 $y_{i}$ 进行排序，优先完成即将到时间的任务；题目要求使用金币最少，如果需要使用金币，一定是使用 $z_{i}$ 最小的方法。

因此使用优先队列对 $z_{i}$ 进行升序，假设某一时刻无法完成某个任务，考虑前面已经被确认可以完成的任务中，选择 $z_{i}$ 最小的第i个任务(选择队头元素，有可能队头元素就是这一次任务本身，需要先push)。对于队头元素仍需考虑 $x_{i}$ 的值是否足够填满该段时间，如果需要的时间比队头大，则计算出费用，将队头元素之间弹出即可；若需要的时间比队头的小，则计算出费用，还需要把队头元素塞回队列。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n;

struct node{
    int z , x , y;
    bool operator<(const node &s)const {
        return z < s.z;
    }
}a[N];

bool cmp(const node a,const node b){
    return a.y < b.y;
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i].z >> a[i].x >> a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    double ans = 0;
    int cur = 0;
    priority_queue<node> pq;
    for(int i=1;i<=n;i++){
        cur += a[i].x;
        pq.push(a[i]);
        if(cur > a[i].y){
            int nd = cur - a[i].y;
            cur = a[i].y;
            while(!pq.empty()){
                if(nd == 0) break;
                auto tmp = pq.top(); pq.pop();
                if(nd > tmp.x){
                    ans += 1.0*tmp.x/tmp.z;
                    nd -= tmp.x;
                }else{
                    ans += 1.0*nd/tmp.z;
                    pq.push({tmp.z,tmp.x-nd,tmp.y});
                    nd = 0;
                }
            }
        }
    }
    printf("%.1lf\n",ans);
    return 0;
}

小C的周末

题面

n个人，每个人只想玩一款游戏。某一款游戏想要开始，必须要求所有玩这一款游戏的人连在同一条圈子里。小C有q条线，每条线都会把两个人连起来，注意一点就行，连的同时还会把与两个人相连的所有人连在一起。

思路

首先两个人合并在一起，肯定是并查集，那么就有一个问题，可能连线的两个人a和b不是玩的同一款游戏的，但是其他与a连接的人c可能与b玩的是同一款游戏。

并查集合并两个人的同时，需要将两个人的圈子里所有玩某款游戏的人合并在一起，但是 $1 e 5 * 1 e 5$ 的数组开不出来，可以选择使用map只存储玩某款游戏的人，最后两个人合并的时候小的合并到大的里面节省时间。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,q;
int wt[N],nd[N],ret[N];
int rt[N];
map<int,int> mp[N]; 

int find(int x){
    return rt[x]==x?x:rt[x]=find(rt[x]);
}

void un(int x,int y){
    int xx = find(x) , yy = find(y);
    if(xx != yy){
        rt[xx] = yy;
    }
}

int main(){
    while(scanf("%d %d %d",&n,&m,&q)!=EOF){
        for(int i=1;i<=m;i++){
            ret[i] = -1;
            nd[i] = 0;
        }
        for(int i=1;i<=n;i++){
            mp[i].clear();
            scanf("%d",&wt[i]);
            rt[i] = i;
            nd[wt[i]]++;
            mp[i][wt[i]]++;
        }
        for(int i=1;i<=q;i++){
            int x,y;
            scanf("%d %d",&x,&y);
            x = find(x) , y = find(y);
            if(mp[x].size() > mp[y].size()){
                swap(x,y);
            }
            rt[x] = y;
            for(auto it=mp[x].begin();it!=mp[x].end();it++){
                mp[y][it->first] += it->second;
                if(mp[y][it->first] == nd[it->first]){
                    ret[it->first] = i;
                }
            }
        }
        for(int i=1;i<=m;i++){
            if(nd[i] == 1){
                puts("0");
            }else{
                cout << ret[i] << endl;
            }
        }
        
    }
    return 0;
}