laekov

贪心。从小到大每个灯泡找个小于等于它的最接近的房间去照。

剩下的照不亮的房间直接换。

剩下的背包空间把已经匹配的差最大的换掉。

第一步要拿堆维护一下。剩下的直接排序。

然后把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);

}

}