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;
}