【洛谷P3076】Taxi

这道题值得好好想一会

我们通过对一些小数据的手算，以及对于每段路程的拆分，可以发现：

1.每个st对应的ed这段路程无论如何都要算上

2.额外还要计算的一段路程，就是“切换”费用

什么是切换费用呢？

我们知道可能会有这样的位置st，到达该位置时，把已经在车上的牛 i 扔下去，载上该处的牛 j 并将它运到其终点ed再回来把牛 i 载上

那么我们就需要再加上每一对abs(ed-st)的和

具体实现，我们需要在st、ed中再加上终点m，起点0,

但是要注意的是，0加到ed里，m加到st里

原因在于我们需要从起点0走到最近的st，从最远的ed走到m

所以0对应的就是min_st，0必然在ed里的第一个；m也一样

最后将st，ed排序，枚举累加即可

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int n,m,st[N],ed[N];

 long long ans=;

 int read(){

     int sum=;

     char ch=getchar();

     while (ch<''||ch>'')

         ch=getchar();

     while (ch>=''&&ch<=''){

         sum=sum*+ch-'';

         ch=getchar();

     }

     return sum;

 }

 int main(){

     n=read();

     m=read();

     for (int i=;i<=n;i++){

         st[i]=read();

         ed[i]=read();

         ans+=abs(st[i]-ed[i]);

     }

     st[n+]=m;//最远的ed开到m

     ed[n+]=;//0开到最近的st

     sort(st+,st+n+);

     sort(ed+,ed+n+);

     for (int i=;i<=n+;i++)

         ans+=abs(ed[i]-st[i]);

     printf("%lld",ans);

     return ;

 }

巴特西

【洛谷P3076】Taxi

最新文章

热门文章