题目描述

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

题目分析

先将两个数组排序 然后从大到小贪心
对于每个房间 先把大于等于这个房间的功率的灯泡扔进一个堆里 然后取最小的即可
如果堆为空 花费一次机会即可
最后还有一波贪心 如果我们还剩下换灯泡的机会 将差值较大的都换成和房间功率正好的

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
long long p[500100],w[500100],ans[500100];
int tmp;
long long sum;
priority_queue<long long>q;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&p[i]),sum+=p[i];
    sort(p+1,p+n+1),sort(w+1,w+n+1);
    tmp=n;
    for(int i=n;i>=1;i--)
    {
        while(tmp&&w[tmp]>=p[i]) q.push(-w[tmp]),tmp--;
        if(q.size()) ans[i]=-q.top()-p[i],q.pop();
        else
        {
            if(!m) 
            {
                printf("NIE");
                return 0;
            }
            m--,ans[i]=0;
        }
    }
    sort(ans+1,ans+n+1);
    for(int i=n;i>=n-m+1&&i>=1;i--) ans[i]=0;
    for(int i=1;i<=n;i++) sum+=ans[i];
    printf("%lld",sum);
    return 0;
}