[FROM WOJ]#3989 PA2014Final Zarowki#3989 PA2014Final Zarowki

151 阅读 0 评论 100 点赞

我是靠谱客的博主勤劳大雁，这篇文章主要介绍[FROM WOJ]#3989 PA2014Final Zarowki#3989 PA2014Final Zarowki，现在分享给大家，希望可以做个参考。

#3989 PA2014Final Zarowki

题面
有n个房间和n盏灯，你需要在每个房间里放入一盏灯。每盏灯都有一定功率，每间房间都需要不少于一定功率的灯泡才可以完全照亮。
你可以去附近的商店换新灯泡，商店里所有正整数功率的灯泡都有售。但由于背包空间有限，你至多只能换k个灯泡。
你需要找到一个合理的方案使得每个房间都被完全照亮，并在这个前提下使得总功率尽可能小。
注意STL堆的内存不能动态回收

输入
第一行两个整数n,k(1<=k<=n<=500000)。

第二行n个整数pi，表示你现有的灯泡的功率。

第三行n个整数wi，表示照亮每间房间所需要的最小功率。

输出
如果无法照亮每间房间，仅输出NIE。
否则输出最小的总功率。

样例输入
6 2
12 1 7 5 2 10
1 4 11 4 7 5

样例输出
33

SOL
看到题面就知道应该贪心做这道题。不过贪心标准稍稍有点棘手。
经过~~简单地~~分析，可以发现答案最小也就是 $sum_{i=1}^{n}w[i]$ 也就是说，我们要尽可能地是我们的答案接近于这个答案。
但是怎样贪心才能保证做到这一点呢？我们首先可以让每个房间都配有一盏功率大于对于她的 $w [i]$ 值的最小 $p [j]$ 的灯泡，毫无疑问，为了实现这步操作，需要给两个数组排一次序。
排完序之后就考虑怎么实现这样的匹配，考虑先满足 $w [i]$ 值较大的房间——因为如果 $w [i]$ 小的房间有多个大于其 $w [i]$ 的灯泡，那么 $w [i]$ 较大的会用掉其中一个，而这个灯泡显然会大于和那个 $w [i]$ 较小的房间匹配的那个灯泡的 $p [j]$ ，于是就先满足 $w [i]$ 较大的较为合理，用堆维护一下就好。
但是肯定会出现不满足情况的时候，这时候就只能用掉一个更换灯泡的机会，至于更换哪个灯泡显然是不需要考虑的，每次对k减1即可，当k<0就不满足条件，然后将灯泡多出来的功率放入一个大根堆，最后把最上面几个灯泡换了就可以了。

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define N 500005
#define int long long
using namespace std;
inline int rd(){
	int data=0;static char c=0;c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')data=(data<<3)+(data<<1)+c-'0',c=getchar();
	return data;
}
int n,k,ans;
int p[N],w[N];
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<int,vector<int>,less<int> >q2;
signed main(){
//	freopen("rand.out","r",stdin);
//	freopen("own.out","w",stdout); 
	n=rd();k=rd();
	for(int register i=1;i<=n;i++){p[i]=rd();}
	for(int register i=1;i<=n;i++){w[i]=rd();}
	sort(p+1,p+n+1);sort(w+1,w+n+1);
	for(int register i=n,j=n;i>=1;i--){
		while(j>0&&w[i]<=p[j]){
			q1.push(p[j]);
			j--;
		}
		if(q1.empty()){
			if(k<=0){
				puts("NIE");
				return 0;
			}			
			k--;
			ans+=w[i];
		}
		else{
			int t=q1.top();
			ans+=t;
			q2.push(t-w[i]);
			q1.pop();
		}
	}
	while(!q2.empty()){
		if(k<=0)break;
		ans-=q2.top();
		q2.pop();
		k--;		
	}
	printf("%lld",ans);
	return 0;
}