Description
有n個房間和n盞燈，你需要在每個房間里放入一盞燈。每盞燈都有一定功率，每間房間都需要不少于一定功率的燈泡才可以完全照亮。?
你可以去附近的商店換新燈泡，商店里所有正整數功率的燈泡都有售。但由于背包空間有限，你至多只能換k個燈泡。?
你需要找到一個合理的方案使得每個房間都被完全照亮，并在這個前提下使得總功率盡可能小。
Input
第一行兩個整數n,k(1<=k<=n<=500000)。?
第二行n個整數pi，表示你現有的燈泡的功率。?
第三行n個整數wi，表示照亮每間房間所需要的最小功率。
Output
如果無法照亮每間房間，僅輸出NIE。?
否則輸出最小的總功率。
Sample Input
6 2 12 1 7 5 2 10 1 4 11 4 7 5?
Sample Output
33?
?
看到數據范圍，想到可能是貪心。
我們先按照燈的功率從小到大排序，然后從小到大依次讓燈去選擇房間。很顯然每個燈都要選擇自己能夠照明的需要功率最大的房間。然后剩下的沒有選擇的房間只能通過購買燈泡來完成。判斷無解也非常容易，如果剩下的房間大于k個就無解。
但是如果剩下房間小于k個，我么顯然可以將之前配對好的燈泡替換了來降低答案值。所以我們開個大根堆，維護配對了的的最大值就可以了。
代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<ctime>
#define ll long long
#define N 500005using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,k;
ll p[N],w[N];
priority_queue<ll>cha;
multiset<ll>s;
multiset<ll>::iterator it;
ll ans;
int main() {n=Get(),k=Get();for(int i=1;i<=n;i++) p[i]=Get();for(int i=1;i<=n;i++) {w[i]=Get();s.insert(w[i]);}sort(p+1,p+1+n);for(int i=1;i<=n;i++) {it=s.upper_bound(p[i]);if(it==s.begin()) continue ;it--;ans+=p[i];cha.push(p[i]-*it);s.erase(it);if(!s.size()) break;}if(s.size()>k) {cout<<"NIE";return 0;}for(it=s.begin();it!=s.end();it++) {ans+=*it;}k-=s.size();for(int i=1;i<=k;i++) {ans-=cha.top();cha.pop();if(!cha.size()) break;}cout<<ans;return 0;
}
?
