Food Stalls （2019 Google Kickstart Round D）

题目链接：https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051061

我。。。。这还能不按照x顺序给出的吗。。。，前两个样例都是顺序给出的，第三个样例我没注意。。。但怎么过了第三个样例啊。。。难顶，分低了还罚时爆炸

我们假设当前选出了k+1个位置，那么这k+1个位置的c是固定加到代价里去的，那么这个时候货物仓库肯定放在中间最好，我之前纠结了一个问题就是加入中间位置有两个地方，那么到底放在哪个，后来发现中间位置有两个的时候放在左边还是右边，距离差都是一样的。

所以我们k1=k/2,k2=k-k1，从左向右枚举食品仓库，然后左边每个地方的值变成 a[i]c-a[i].x，右边每个地方的权值变成a[i].c+a[i].x。

那么当前食品仓库放在 i 号位置，所能得到的最小代价tmp=左边最小k1个值+右边最小的k2个值+k1*a[i]-k2*a[i]。

左边最小k1个值用一个堆维护，右边最小k2个值用一个堆表示没进入最小k2个的值和下标，再用一个set表示哪些下标在最小的k2个中。每次枚举食品仓库的位置i+1,就只要两边都维护一次,logn复杂度，总复杂度就是nlogn

#include<bits/stdc++.h>
#define maxl 300010

using namespace std;

int n,k,m,cas;
struct node
{
	int x,c;
}a[maxl];
typedef pair<int,int> p;
priority_queue<int> q1;
set <int> s;
priority_queue<p,vector<p>,greater<p> > q2;
long long ans;

inline bool cmp(const node &x,const node &y)
{
	return x.x<y.x;
}

inline void prework()
{
	scanf("%d%d",&k,&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i].x);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i].c);
	sort(a+1,a+1+n,cmp);
} 

inline void mainwork()
{
	while(!q1.empty()) q1.pop();
	while(!q2.empty()) q2.pop();
	s.clear();
	int k1=k/2,k2=k-k1;
	long long tmp=a[k1+1].c;p d;
	for(int i=1;i<=k1;i++)
	{
		q1.push(a[i].c-a[i].x);
		tmp+=-a[i].x+a[i].c; 
	}
	for(int i=n;i>=k1+2;i--)
		q2.push(make_pair(a[i].c+a[i].x,i));
	for(int i=1;i<=k2;i++)
	{
		d=q2.top();q2.pop();
		tmp+=d.first;
		s.insert(d.second);
	}
	ans=tmp+1ll*k1*a[k1+1].x-1ll*k2*a[k1+1].x;
	for(int i=k1+2;i<=n-k2;i++)
	{
		tmp-=a[i-1].c;tmp+=a[i].c;
		if(!q1.empty())
		if(a[i-1].c-a[i-1].x<q1.top())
		{
			tmp-=q1.top();q1.pop();
			tmp+=a[i-1].c-a[i-1].x;
			q1.push(a[i-1].c-a[i-1].x);
		}
		if(s.begin()!=s.end())
		if((*s.begin())==i)
		{
			tmp-=a[i].c+a[i].x;
			s.erase(s.begin()); 
			do
			{
				d=q2.top();q2.pop();
			}while(d.second<=i);
			tmp+=d.first;
			s.insert(d.second);
		}
		ans=min(ans,tmp+1ll*k1*a[i].x-1ll*k2*a[i].x);
	}
}

inline void print()
{
	printf("Case #%d: ",cas);
	printf("%lld\n",ans);
}

int main()
{
	int t;
	scanf("%d",&t);
	for(cas=1;cas<=t;cas++)
	{ 
		prework();
		mainwork();
		print();
	}
	return 0;
}