BZOJ3728 PA2014Final Zarowki

贪心题目

然而我的贪心又是错的,但是这一次至少大体思路对了

我的错误思路:

把数组分别排序,然后一一对应,如果小就换,最后如果还有机会,就在剩下的大的选择差值最大的减去

正确思路:

将\(p\)数组排序,对于每个数,都找到小于等于他的最大的数,然后把他们的差值扔到堆里

找最大的数可以利用两个数组排序之后的单调性或者直接暴力上multiset去解决

如果最后还有超过\(k\)个房间没有被匹配,说明无解

否则就换成对应功率的灯泡

有过还有剩余机会

就把堆中的对应的数抹平

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<set>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 3;
int p[N];
int w[N];
multiset <int> s;
priority_queue <int> q;
int n,k;
LL ans;
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
int main(){
    multiset<int>::iterator it;
    n = read(),k = read();
    for(int i = 1;i <= n;++i) p[i] = read();
    for(int i = 1;i <= n;++i){
        w[i] = read();
        s.insert(w[i]); 
    }
    sort(p + 1,p + n + 1);
    for(int i = 1;i <= n;++i){
        it = s.upper_bound(p[i]);
        if(it == s.begin()) continue;
        it--;
        ans += p[i];
        q.push(p[i] - *it);
        s.erase(it);
    } 
    if(s.size() > k){printf("NIE\n");return 0;}
    for(it = s.begin();it != s.end();it++){
        ans += *it;
        k--;
        q.push(0);
    }
    while(k != 0){
        ans -= q.top();
        q.pop();
        k--;    
    }
    printf("%lld\n",ans);
    return 0;
}