贪心。从小到大每个灯泡找个小于等于它的最接近的房间去照。
剩下的照不亮的房间直接换。
剩下的背包空间把已经匹配的差最大的换掉。
第一步要拿堆维护一下。剩下的直接排序。
然后把nie写成-1了，no save。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long di;
#ifdef WIN32
#define difmt "%I64d"
#else
#define difmt "%lld"
#endif
const int maxn = 500009;
int _d_;
#define readInt(_x_) { \
int& _s_ = _x_; \
while (!isdigit(_d_ = getchar())); \
_s_ = 0; \
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
}
int n, k, p[maxn], w[maxn], x[maxn], t;
di ans;
int main() {
readInt(n);
readInt(k);
for (int i = 0; i < n; ++ i)
readInt(p[i]);
for (int i = 0; i < n; ++ i)
readInt(w[i]);
sort(p, p + n);
sort(w, w + n);
t = 0;
ans = 0;
for (int i = 0; i < n; ++ i)
ans += w[i];
for (int i = 0, j = 0, th = 0; i < n && k >= 0; ++ i) {
for (; j < n && w[j] <= p[i]; w[th] = w[j ++], push_heap(w, w + (++ th)));
if (th) {
x[t ++] = p[i] - w[0];
pop_heap(w, w + (th --));
}
else
-- k;
}
if (k < 0)
puts("NIE");
else {
sort(x, x + t);
for (int i = t - k - 1; i >= 0; -- i)
ans += x[i];
printf(difmt "\n", ans);
}
}