3728: PA2014Final Zarowki
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 189 Solved: 92
[Submit][Status][Discuss]
Description
有n个房间和n盏灯，你需要在每个房间里放入一盏灯。每盏灯都有一定功率，每间房间都需要不少于一定功率的灯泡才可以完全照亮。
你可以去附近的商店换新灯泡，商店里所有正整数功率的灯泡都有售。但由于背包空间有限，你至多只能换k个灯泡。
你需要找到一个合理的方案使得每个房间都被完全照亮，并在这个前提下使得总功率尽可能小。
Input
第一行两个整数n,k(1<=k<=n<=500000)。
第二行n个整数p[i](1<=p[i]<=10^9)，表示你现有的灯泡的功率。
第三行n个整数w[i](1<=w[i]<=10^9)，表示照亮每间房间所需要的最小功率。
Output
如果无法照亮每间房间，仅输出NIE。
否则输出最小的总功率。
Sample Input
6 2
12 1 7 5 2 10
1 4 11 4 7 5
12 1 7 5 2 10
1 4 11 4 7 5
Sample Output
33
HINT
解释：将2和10换成4和4。配对方案为1-1,4-4,4-4,5-5,7-7,11-12。
Source
一道比较简单的贪心题。。
我们先考虑购买次数最少的情况下要花费多少功率。。。对于这个我们可以贪心做。。先将p和w从大到小排序。。然后枚举每一个w[i]。。在比他大的所有p中选一个最小的。。如果没有就要耗费一次机会加上。。答案加上w[i]。。这个可以用堆实现。。
然后我们就得到了购买次数最少情况下的答案。。然后对于剩下的次数我们也要把它利用起来。。
我们可以另开一个堆记录每一次的w和p的差值。。然后将差值最大的几次去掉、、
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int a[500010],n,K,sum,b[500010];
long long ans;
priority_queue <int> q;
bool cmp(int a,int b){return a>b;}
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
struct Heap{
int cnt,hp[500010];
void Up(int pos){
while (pos>1 && hp[pos]<hp[pos>>1]){
swap(hp[pos>>1],hp[pos]);
pos>>=1;
}
}
void Down(int pos){
for (int p=pos;;){
if ((pos<<1)<=cnt && hp[pos<<1]<hp[p]) p = pos<<1;
if ((pos<<1|1)<=cnt && hp[pos<<1|1]<hp[p]) p = pos<<1|1;
if (pos==p) return;
swap(hp[p],hp[pos]);
pos = p;
}
}
void Push(int v){hp[++cnt] = v;Up(cnt);}
void Pop(){hp[1] = hp[cnt--];Down(1);}
int Top(){return hp[1];}
bool Empty(){return cnt==0;}
} heap;
int main(){
n = read();K = read();
for (int i=1;i<=n;i++) b[i] = read();
for (int i=1;i<=n;i++) a[i] = read();
sort(a+1,a+1+n,cmp);sort(b+1,b+1+n,cmp);
int pos = 1;
for (int i=1;i<=n;i++){
while (b[pos]>=a[i]) heap.Push(b[pos++]);
if (heap.Empty()){sum++;ans+=a[i];}
else {ans+=heap.Top();q.push(heap.Top()-a[i]);heap.Pop();}
}
if (sum<=K){
while (sum<K && !q.empty()) ans-=q.top(),q.pop(),sum++;
printf("%lld",ans);
}
else printf("NIE");
}
评论 (0)
