记录编号	597413	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	魔法传送阵	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	1.921 s
提交时间	2024-11-27 17:44:04	内存使用	4.78 MiB

#include <bits/stdc++.h>
using namespace std;
struct dian{
	int a,b;
}p[1000010];
int k,n,tot,cnt;
long long ans,haf[2][1000010],s1,s2,pl[1000010];  
priority_queue<int> q1;
priority_queue<int,vector<int>,greater<int> > q2;
bool cmp(dian x,dian y) 
{
	return x.a+x.b<y.a+y.b;    
}
int main() 
{
	freopen("bridge.in","r",stdin);
	freopen("bridge.out","w",stdout);
	scanf("%d%d",&k,&n);
	for(int i=1;i<=n;i++) 
	{
		long long x1,x2;
		char c1,c2;
		scanf(" %c%lld %c%lld",&c1,&x1,&c2,&x2);
		if(c1==c2) 
		{
			ans+=abs(x2-x1);
		} 
		else 
		{
			ans++;
			p[++tot].a=x1;
			p[tot].b=x2;
			pl[++cnt]=x1;
			pl[++cnt]=x2;
		}
	}
	if(k==1)
	{
		sort(pl+1,pl+cnt+1);
		long long pos=pl[cnt/2];
		for(int i=1;i<=cnt;i++) 
		{
			ans+=abs(pl[i]-pos);
		}
		printf("%lld",ans);
	} 
	else 
	{
		sort(p+1,p+tot+1,cmp);
		for(int i=1;i<=tot;i++) 
		{
			q1.push(p[i].a);
			q1.push(p[i].b);
			s1+=p[i].a+p[i].b;
		    s2+=q1.top();
			s1-=q1.top();
			q2.push(q1.top());
			q1.pop();
			if(q1.top()>q2.top()) 
			{    
				int t=q2.top();
				int l=q1.top();
				q2.pop();
				q1.pop();
				q2.push(l);
				q1.push(t);
				s1+=t-l;
				s2-=t-l;
			}
           	haf[0][i]=s2-s1;    
    	}
    	while(!q1.empty()) 
		{
    		q1.pop();
		}
		while(!q2.empty()) 
		{
    		q2.pop();
		}
		s1=0;
		s2=0;
		for(int i=tot;i>=1;i--) 
		{
			q1.push(p[i].a);
			q1.push(p[i].b);
			s1+=p[i].a+p[i].b;
			s2+=q1.top();
			s1-=q1.top();
			q2.push(q1.top());
			q1.pop();
			if(q1.top()>q2.top()) 
			{    
				int t=q2.top();
				int l=q1.top();
				q2.pop();
				q1.pop();
				q2.push(l);
				q1.push(t);
				s1+=t-l;
				s2-=t-l;
			}
           	haf[1][i]=s2-s1;    
		}
		long long mi=1e18;
		for(int i=1;i<=tot+1;i++) 
		{
			mi=min(mi,haf[0][i-1]+haf[1][i]);
		}
		printf("%lld",mi+ans);    
	}
	return 0;
}