BZOJ3728 PA2014Final Zarowki

2014.12.23 15:30 Tue| 4 visits oi_2015| 2015_刷题日常| Text

本来说好要推莫比乌斯反演的公式的 T^T 现在又开始做这种水题了……

Solution

显然是贪心嘛 = = 这里没什么好说的。用multiset维护每一个已有的灯泡能点亮的需求量最大的房子,然后用优先队列维护能够节省的最大功率。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 500005

int n,k,p[N];
long long ans;
priority_queue<int> q;
multiset<int> s;
multiset<int>::iterator it;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        p[i]=read();
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++)
        s.insert(read());
    for(int i=1;i<=n;i++)
    {
        it=s.upper_bound(p[i]);
        if(it--==s.begin()) continue;
        q.push(p[i]-*it), s.erase(it), ans+=p[i];
    }
    if(s.size()>k) puts("NIE"), exit(0);
    for(it=s.begin();it!=s.end();++it)
        k--, ans+=*it;
    while(k--)
        ans-=q.top(), q.pop();
    cout<<ans<<endl;
}