[PA2014]Żarówki
题目大意：
有\(n(n\le5\times10^5)\)个房间和\(n\)盏灯，你需要在每个房间里放入一盏灯。每盏灯都有一定功率\(p_i\)，每间房间都需要功率不小于\(w_i\)的灯泡才可以完全照亮。
你可以去附近的商店换新灯泡，商店里所有正整数功率的灯泡都有售。但由于背包空间有限，你至多只能换\(k\)个灯泡。
你需要找到一个合理的方案使得每个房间都被完全照亮，并在这个前提下使得总功率尽可能小。
思路：
贪心，将房间按\(w_i\)从大到小排序。找到最小的能满足该房间的灯。如果不存在，就花一次换灯泡的机会，换来一个功率恰好等于\(w_i\)的灯泡。最后如果还有多的机会，就将浪费功率最多的灯泡换掉。
源代码：
#include<set>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<functional>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=5e5+1;
std::multiset<int> p,t;
int w[N];
int main() {
const int n=getint();
int k=getint();
for(register int i=1;i<=n;i++) {
p.insert(getint());
}
for(register int i=1;i<=n;i++) {
w[i]=getint();
}
std::sort(&w[1],&w[n]+1,std::greater<int>());
int64 ans=0;
for(register int i=1;i<=n;i++) {
std::multiset<int>::iterator it=p.lower_bound(w[i]);
if(it==p.end()) {
if(!k--) {
puts("NIE");
return 0;
}
ans+=w[i];
} else {
ans+=*it;
if(*it-w[i]) {
t.insert(*it-w[i]);
}
p.erase(it);
}
}
while(k--&&!t.empty()) {
ans-=*t.rbegin();
t.erase(--t.end());
}
printf("%lld\n",ans);
return 0;
}