當并查集遇上貪心【UVA1623，UVA11134，POJ1456】

導入

你，是否在想到貪心政策卻無法找到“比x大/小的第一個空位”而煩惱不已？

你，是否因為沒有高效的算法而不斷TLE？

你需要的，僅僅隻是一個4行代碼的并查集而已。

當并查集遇上貪心——

一切事情似乎都那麼美妙！

好吧以上一段廢話隻是說明并查集在解決“尋找比x大/小的第一個滿足條件的位置，并占用這個位置”的貪心問題上很優秀而已

UVA1623

題目大意

某城市有n個湖，一開始全是滿的。接下來有m天，每天在一個湖裡會下暴雨，如果下雨的湖是空的就會變滿，是滿的就會發生水災。城市裡有一條龍，在不下雨的天可以喝幹一個滿的湖，問龍要怎麼喝水才能防止發生水災（輸出不下雨的天裡龍喝的湖的編号，不喝輸出“0”。）

題目分析

很容易想到一個貪心政策：假如今天在湖x上下雨了，我們找到湖x上一次被填滿的時間，然後在這個時間後第一個晴天讓龍喝了x的水。

但是此題資料範圍很大，需要高效維護。怎麼辦？上并查集！

f[x]表示：x之後第一個晴天。首先用并查集的路徑壓縮找到f[x]，然後令f[x]=find(x+1)即可（find是一邊找根一邊路徑壓縮的函數），複雜度常數級别，比用隊列什麼維護的不知道高明快到哪裡去了。

代碼

用時200ms。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
    int q=;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*+ch-'0',ch=getchar();
    return q;
}
const int N=+;
int T,n,m;
int f[N],a[N],ans[N],lake[N];
int find(int x) {
    if(f[x]==x) return x;
    f[x]=find(f[x]);return f[x];
}
int work() {
    int i,x;
    for(i=;i<=n;++i) lake[i]=;
    for(i=;i<=m;++i) {
        if(!a[i]) continue;
        x=find(lake[a[i]]);
        if(x<=i) ans[x]=a[i],f[x]=find(x+);
        else return ;
        lake[a[i]]=i;
    }
    puts("YES");
    for(i=;i<=m;++i)
        if(!a[i])printf("%d ",ans[i]);
    puts("");
}
int main()
{
    int i,las;T=read();
    while(T--) {
        n=read(),m=read();
        for(i=;i<=m;++i) ans[i]=,a[i]=read();
        las=m+,f[m+]=m+;
        for(i=m;i>=;--i) {
            if(!a[i]&&i!=) las=i;
            f[i]=las;
        }
        if(!work()) puts("NO");
    }
    return ;
}
           

UVA11134

題目大意

在n*n的棋盤上放n個車，使任意兩車不共行或共列。第i個車必須放在以( x1 , y1 )為左上角( x2 , y2 )為右下角的矩陣裡。

題目分析

首先發現某一個車所在位置的行和列可以分開考慮。

好的，那麼題目變成了求兩次：給定n個區間（ [x1,x2] 或 [y1,y2] ），在每個區間裡放一個[1,n]的整數且這些整數互不相同。

會發現區間用右端點為第一關鍵字，左端點為第二關鍵字，從小到大排序後，一個一個處理，目前區間選擇：還沒有被用過的，離左端點盡可能近的一個數會比較好（因為以後的區間會在“後面一點”，是以小的數用處會越來越小）。

那麼自然是用f[x]表示：大于等于x的沒有被用過的數。

那麼處理就和上題類似啦。

代碼

用時0ms。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
    int q=;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*+ch-'0',ch=getchar();
    return q;
}
const int N=;
struct node{int l,r,id;}a[N],b[N];
int n,xx[N],yy[N],f[N];
bool cmp(node x,node y) {
    if(x.r==y.r) return x.l<y.l;
    return x.r<y.r;
}
int find(int x) {
    if(f[x]==x) return x;
    f[x]=find(f[x]);return f[x];
}
int work1() {
    for(int i=;i<=n+;++i) f[i]=i;
    for(int i=;i<=n;++i) {
        int kl=find(a[i].l);
        if(kl<=a[i].r) xx[a[i].id]=kl,f[kl]=find(kl+);
        else return ;
    }
    return ;
}
int work2() {
    for(int i=;i<=n+;++i) f[i]=i;
    for(int i=;i<=n;++i) {
        int kl=find(b[i].l);
        if(kl<=b[i].r) yy[b[i].id]=kl,f[kl]=find(kl+);
        else return ;
    }
    return ;
}
int main()
{
    while("I am cute.") {//其實就是while(1)
        n=read();if(!n) break;
        for(int i=;i<=n;++i) {
            a[i].l=read(),b[i].l=read();
            a[i].r=read(),b[i].r=read();
            a[i].id=b[i].id=i;
        }
        sort(a+,a++n,cmp),sort(b+,b++n,cmp);
        if(!work1()){puts("IMPOSSIBLE");continue;}
        if(!work2()){puts("IMPOSSIBLE");continue;}
        for(int i=;i<=n;++i) printf("%d %d\n",xx[i],yy[i]);
    }
    return ;
}
           

POJ1456

題目大意

超市要銷售一些東西，每天隻能銷售一個。給出每件商品的銷售後的價格和銷售的期限（即要在期限内銷售出去），求銷售的最大獲利。

題目分析

先把商品按照價格從大到小排序，然後處理，一件商品在其銷售期限内的第一個沒有銷售任務的日子用來銷售這件商品。如果找不到空的日子，就不銷售這件商品。

用并查集維護“一件商品在其銷售期限内的第一個沒有銷售任務的日子”

代碼

時間：63ms（沒有加讀入優化QAQ）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
const int N=;
int n,ans;
struct node{int w,t;}a[N];
int f[N];
bool cmp(node x,node y){return x.w>y.w;}
int find(int x){
    if(f[x]==x)return x;
    f[x]=find(f[x]);return f[x];
}
int main()
{
    int i,j,r1,r2;
    while(scanf("%d",&n)!=EOF){
        for(i=;i<=n;++i)scanf("%d%d",&a[i].w,&a[i].t);
        sort(a+,a++n,cmp);
        for(i=;i<=;++i)f[i]=i;
        ans=;
        for(i=;i<=n;++i){
            r1=find(a[i].t);
            if(r1){
                r2=find(r1-);
                f[r1]=r2,ans+=a[i].w;
            }
        }
        printf("%d\n",ans);
    }
    return ;
}
           

練習題

–由于某些特殊原因，此題暫時留白–