首页 > 代码库 > 【51nod 1331】狭窄的通道
【51nod 1331】狭窄的通道
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数据范围变大后实测跑得飞快。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 long long ans,sum,summ; 7 int T,n,l; 8 struct node{int s,t;}a[105]; 9 int read() 10 { 11 int x=0,f=1;char c=getchar(); 12 while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} 13 while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} 14 return x*f; 15 } 16 bool cmp1(node a,node b){return a.s<b.s;} 17 bool cmp2(node a,node b){return a.t<b.t;} 18 bool okey(int l1,int r1,int l2,int r2) 19 { 20 int mx=0,mn=1e9; 21 for(int i=l1;i<=r1;i++)mx=max(mx,a[i].t); 22 for(int i=l2;i<=r2;i++)mn=min(mn,a[i].t); 23 return mx<mn; 24 } 25 void cond1() 26 { 27 for(int i=0;i<=n;i++) 28 { 29 if(!okey(0,i,i+1,n))continue; 30 int cut=n+1;sum=0;summ=0; 31 for(int j=0;j<=i;j++)sum+=a[j].s+a[j].t; 32 for(int j=i+1;j<=n;j++) 33 { 34 if(!okey(i+1,j,j+1,n)){cut=j;break;} 35 summ+=abs(a[j].s-a[j].t); 36 } 37 sum+=summ; 38 for(int j=cut;j<=n;j++)sum+=2*l-a[j].s-a[j].t; 39 ans=min(ans,sum); 40 } 41 } 42 void solc(int x) 43 { 44 sort(a+1,a+x+1,cmp2); 45 sort(a+x+1,a+n+1,cmp2); 46 int li=1,ri=x+1,rj=x+1; 47 long long sum1=0,sum2; 48 while(li<=x&&ri<=n) 49 { 50 sum2=0; 51 while(li<=x&&a[li].t<a[ri].t)li++; 52 if(li==x+1)break; 53 while(ri<=n&&a[ri].t<a[li].t)ri++; 54 for(int i=li;i<=x;i++)sum2+=2*(l-a[i].t); 55 ans=min(ans,sum+sum1+sum2); 56 for(int i=rj;i<ri;i++)sum1+=2*a[i].t; 57 if(a[ri].t>a[x].t)break; 58 rj=ri;li++; 59 } 60 ans=min(ans,sum+sum1); 61 } 62 void cond2() 63 { 64 for(int i=1;i<=n-1;i++) 65 { 66 sort(a+1,a+n+1,cmp1); 67 sum=0; 68 for(int j=1;j<=i;j++)sum+=a[j].s+a[j].t; 69 for(int j=i+1;j<=n;j++)sum+=2*l-a[j].s-a[j].t; 70 if(sum>=ans)continue; 71 if(okey(1,i,i+1,n))continue; 72 solc(i); 73 } 74 } 75 void solve() 76 { 77 n=read();l=read();ans=1e15; 78 for(int i=1;i<=n;i++)a[i].s=read(),a[i].t=read(); 79 a[n+1].s=a[n+1].t=l; 80 sort(a+1,a+n+1,cmp1); 81 cond1(); 82 cond2(); 83 printf("%lld\n",ans); 84 } 85 int main() 86 { 87 T=read(); 88 while(T--)solve(); 89 return 0; 90 }
起点枚举划分这个……直接枚举计算就好了，主要问题在解决冲突。
我直接拿上面那个例子的正确过程来解释吧。
将编号为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进入下一轮计算，直到所有的冲突都被解决才在最后更新答案。
大概就这样咯。祝玩的愉快
【51nod 1331】狭窄的通道