Description
有一个长为L的狭窄通道，我们假设这个通道在x轴上，其两个出口分别在x=0与x=L处。在这个通道里有N只狼，第i只狼有一个初始位置ai,它想到达位置bi（0<=i<N）。但是这个通道太狭窄了不能允许两只狼相互交换位置他们的位置，因此如果两只狼需要交换它们的位置他们需要同时离开这个通道到x=0或x=L处在那里重新安排进通道的顺序。在x<=0与x>=L处空间足够大可以装下任意数量的狼。那么所有的狼想从ai到bi它们总共最少走多远的距离，输出这个距离。
Input
多组测试数据，第一行一个整数T，表示测试数据个数，其中1<=T<=15. 之后有T组相同结构的测试数据： 每组数据第一行两个整数N，L，其中1<=N<=50,2<=L<=1,000,000(即10^6) 之后N行，每行两个整数ai与bi，其中1<=ai，bi<=L-1,且保证所有的狼的起点ai各不相同且终点bi也各不相同。
Output
每组测试数据一行输出，即所有狼在通道中运动的最小距离。
Input示例
2
2 5
1 3
2 4
2 10
3 8
9 6
Output示例
4
14
知道这道题是因为无。比。良。心。的SRM-03=v=
AC的人数太少……网上根本找不到什么正经的题解，于是只能靠自己瞎yy
然后，来写一篇正（luan）经（gao）的题解好了✔
先把所有的狼按起点从小到大sort一发，编号分别为1~n，这是一切的开始（雾。
首先，依据题意，所有的狼可以全往左走或是全往右走而不会造成冲突（显然。
然后，我们可以把所有的狼按起点分为左中右三部分，这三部分中狼的数量可以为0。且中间部分的狼，本身不互相冲突且不与左右冲突，即它们可以直接从起点走到终点。这时候，有一种解决方案为：左边的狼先全部移向0，再移向各自终点；中间的狼直接从各自起点移向终点；右边的狼先全部移向L，再移向各自终点。比如样例，还有类似下面这种：（图丑将就qwq
代码还是很好码的……思路就是先枚举左边部分的狼，再计算中间部分的狼（贪心 ，显然中间部分的狼越多越好；所以我们只需要顺序枚举下去，直到出现冲突为止），然后计算总代价并更新答案。
另，判断方案可行的方法是，左边最右的终点在右边最左的终点的左边（看起来很绕？？？手动画一下图吧w
你以为这样就结束了吗
样例过了？兴奋地交了？什么？只过了七个点？
再来看一组数据咯（LLQ大佬找出来的，orz
1 5 11 5 3 3 4 1 10 7 9 9 1
这组数据，正确答案是48。
过程如下：先将编号为1、2、3的狼移向0，编号为4、5的狼移向L，总代价为15；再将编号为1的狼移向L，将编号为5的狼移向0，总代价累计37；最后将所有的狼移向各自终点，答案为48。显然不满足我们之前的思路，因为狼会两边跑（惊不惊喜 意不意外 开不开心=v=
如果说，我们之前讨论的是情况1，那么我们现在需要讨论情况2。
情况2可以用网络流写，具体右拐@yy大佬
现在我们来讲枚举+贪心。（为了想这东西期末统考挂科了，很气
流程大概是：按起点枚举划分，左边的移向0，右边的移向L → 解决终点的冲突问题。简单地说就是，先按起点划，左往左右往右；再按终点划，左边的终点全在右边的终点的左边，即不会造成冲突。
（在写完之后看了一下葱神的代码，发现其实是可以直接枚举分割点的，代码会简洁很多。
好吧还是打算解释一下自己的思路，毕竟SRM-04数据范围变大后实测跑得飞快。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
long long ans,sum,summ;
int T,n,l;
struct node{int s,t;}a[];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
bool cmp1(node a,node b){return a.s<b.s;}
bool cmp2(node a,node b){return a.t<b.t;}
bool okey(int l1,int r1,int l2,int r2)
{
int mx=,mn=1e9;
for(int i=l1;i<=r1;i++)mx=max(mx,a[i].t);
for(int i=l2;i<=r2;i++)mn=min(mn,a[i].t);
return mx<mn;
}
void cond1()
{
for(int i=;i<=n;i++)
{
if(!okey(,i,i+,n))continue;
int cut=n+;sum=;summ=;
for(int j=;j<=i;j++)sum+=a[j].s+a[j].t;
for(int j=i+;j<=n;j++)
{
if(!okey(i+,j,j+,n)){cut=j;break;}
summ+=abs(a[j].s-a[j].t);
}
sum+=summ;
for(int j=cut;j<=n;j++)sum+=*l-a[j].s-a[j].t;
ans=min(ans,sum);
}
}
void solc(int x)
{
sort(a+,a+x+,cmp2);
sort(a+x+,a+n+,cmp2);
int li=,ri=x+,rj=x+;
long long sum1=,sum2;
while(li<=x&&ri<=n)
{
sum2=;
while(li<=x&&a[li].t<a[ri].t)li++;
if(li==x+)break;
while(ri<=n&&a[ri].t<a[li].t)ri++;
for(int i=li;i<=x;i++)sum2+=*(l-a[i].t);
ans=min(ans,sum+sum1+sum2);
for(int i=rj;i<ri;i++)sum1+=*a[i].t;
if(a[ri].t>a[x].t)break;
rj=ri;li++;
}
ans=min(ans,sum+sum1);
}
void cond2()
{
for(int i=;i<=n-;i++)
{
sort(a+,a+n+,cmp1);
sum=;
for(int j=;j<=i;j++)sum+=a[j].s+a[j].t;
for(int j=i+;j<=n;j++)sum+=*l-a[j].s-a[j].t;
if(sum>=ans)continue;
if(okey(,i,i+,n))continue;
solc(i);
}
}
void solve()
{
n=read();l=read();ans=1e15;
for(int i=;i<=n;i++)a[i].s=read(),a[i].t=read();
a[n+].s=a[n+].t=l;
sort(a+,a+n+,cmp1);
cond1();
cond2();
printf("%lld\n",ans);
}
int main()
{
T=read();
while(T--)solve();
return ;
}
起点枚举划分这个……直接枚举计算就好了，主要问题在解决冲突。
我直接拿上面那个例子的正确过程来解释吧。
将编号为1、2、3的狼移向0，编号为4、5的狼移向L之后，呈现出如上图情况。显然，他们在跑向各自终点的过程中会出现冲突，所以需要调整。
以下是对solc函数的解释：起点分割点（即x）左右，分别按终点顺序sort。li为左边第一只狼，ri为右边第一只狼。顺序枚举，直到li与ri发生冲突：在图中，li为1，ri为3。然后对ri进行调整，即把所有与li冲突的ri打包起来算，提高效率。为了解决冲突：1、把所有li右移，计算代价sum2，此时解决了所有冲突，可以直接更新答案；2、把冲突的ri左移，因为此时只解决了一部分冲突，所以我们需要以计算好的sum+sum1进入下一轮计算，直到所有的冲突都被解决才在最后更新答案。
大概就这样咯。祝玩的愉快