好吧其实set还是太会= =。。
3728: PA2014Final Zarowki
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 121 Solved: 58
[Submit][Status]
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
每个灯泡显然如果有和它要求功率相同的房间，那么这个灯泡对应那个房间
那么对于每个灯泡我们找第一个要求<=它的功率的房间
暂时先放着，记录下2者相差的值
灯泡功率太小以及房间要求太高的这些直接换掉
剩下能换的把前面相差最多的换掉
然后还有个问题
假设有2个房间要求为1 5
有2个灯泡功率为6 10
还能换一次
如果开始的时候用6匹配1，用10匹配5
那么最后替换只会使答案减少5（10换成5或6换成1）
但是最优解是:10换成1匹配1,6匹配5
所以开始的时候要先把灯泡排序。。（想了好久。。。一直想成从大到小做。。）
恩好吧写题解只是为了set
恩好吧前面一点都没提到。。。
不管了= =
#include <cstdio>
#include <algorithm>
#include <set>
#define maxn 500005
using namespace std;
struct node{int id;long long val;}y;
struct Node{
inline bool operator ()(node a,node b){
return (a.val<b.val)||(a.val==b.val&&a.id<b.id);
}
};
set<node,Node>S;
set<node,Node>::iterator O;
int a[maxn],b[maxn],c[maxn],d,e,f,g,i,j,k,l,m,n;
long long h;
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(i=1;i<=n;i++){
scanf("%d",&b[i]);
y.id=i;
y.val=b[i];
S.insert(y);
}
for(i=1;i<=n;i++){
y.val=a[i]+1;y.id=0;
O=S.lower_bound(y);
if(O==S.begin())continue;
O--;
h+=a[i];c[++c[0]]=a[i]-(*O).val;
S.erase(O);
}
int kk=S.size();
if(kk>m){printf("NIE");return 0;}
for(i=1;i<=kk;i++){
y.val=0;y.id=0;
O=S.lower_bound(y);
h+=(*O).val;
S.erase(O);
}
sort(c+1,c+1+c[0]);m-=kk;
for(;m&&c[0];m--,c[0]--)h-=c[c[0]];
printf("%lld",h);
return 0;
}
评论 (0)
