LOJ2514 CEOI2011 Hotel 贪心

传送门

---

考虑一个贪心：对于所有人群按照收益从大到小排序，对于每一个人群找到当前能够选择的代价最小的房间成为一组可行订单（如果没有就不可行），最后将这些订单按照收益排序，选其中正的前(o)大即可。找代价最小的房间可以使用并查集，因为有偏序关系所以可以直接二分。

考虑其正确性：对于两个人群(i,j(v_i > v_j))，在我们的算法中会先给(i)分配房间，再给(j)分配房间。如果(i)分配的房间会影响(j)分配房间的选择，那么反过来先选(j)再选(i)也会导致(i)受到同样的影响。所以顺序不会影响最终匹配的个数。

而如果最终方案中(i)和(j)只能选择一个，那么一定会选择(i)和(ij)都能选的房间中代价较低的更优，这在算法中已经体现了；而如果同时选择了(i,j)，那么(i)和(j)的房间互换不会影响答案，所以如何分配都可以。

#include<bits/stdc++.h>
using namespace std;

#define int long long
inline int read(){
    int a = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)){
        if(c == '-') f = 1;
        c = getchar();
    }
    while(isdigit(c)){
        a = a * 10 + c - 48;
        c = getchar();
    }
    return f ? -a : a;
}

const int MAXN = 5e5 + 3;
#define PII pair < int , int >
vector < int > price;
vector < PII > room , peo;
int N , M , K , fa[MAXN];

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

bool cmp(PII a , PII b){return a.first > b.first;}
bool cmp1(int a , int b){return a > b;}

signed main(){
    #ifndef ONLINE_JUDGE
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    #endif
    N = read(); M = read(); K = read();
    for(int i = 0 ; i < N ; ++i){
        int a = read() , b = read();
        room.push_back(PII(b , a));
        fa[i] = i;
    }
    fa[N] = N;
    sort(room.begin() , room.end());
    for(int i = 1 ; i <= M ; ++i){
        int a = read() , b = read();
        peo.push_back(PII(a , b));
    }
    sort(peo.begin() , peo.end() , cmp);
    for(auto t : peo){
        int pos = find(lower_bound(room.begin() , room.end() , PII(t.second , 0)) - room.begin());
        if(pos != N){
            fa[pos] = pos + 1;
            price.push_back(t.first - room[pos].second);
        }
    }
    sort(price.begin() , price.end() , cmp1);
    long long sum = 0;
    for(int i = 0 ; i < K && i < price.size() ; ++i)
        if(price[i] > 0)
            sum += price[i];
    cout << sum;
    return 0;
}