火災逃生（一維版）

題目傳送門

Description

某天晚上，軟院某條狹窄的走廊突然發生了火災，該走廊隻有首尾兩個出口，且因為過于狹窄，兩個人不能并排。

假設t=0的時候發生了火災，此時有NN個人在長度為LL的走廊裡，走廊的最左端的坐标是(0,0)(0,0)，最右端的坐标是(L，0)， 第i個人的位置是(Di，0)。面朝左邊或者右邊，用0和1分别表示面朝左邊和右邊。假設從火災發生的時刻開始，每個人都朝着t=0時面朝的方向以1的速度前進。當兩個人相遇的時候兩個人會立馬掉頭回跑。為了所有人的安全，請計算出所有人離開走廊時的時刻。初始狀态下不會有兩個人在同一個位置。

Input

第一行有一個整數 T （ T &lt; 10 ） T（T&lt;10） T（T<10）表示有TT個案例，每個案例的第一行有兩個整數N(0<N<10^5)N(0<N<10

5

)和L(0<L<10^5)L(0<L<10

5

)，意義如上所述，接下來是NN行，第ii行有兩個數D_iD

i

​ (0<Di<L0<Di<L，表示第ii個人的位置是(Di,0))(Di,0))和zz（0或1，0表示面朝向左，1表示面朝向右）。

Output

請輸出所有人都離開走廊的時刻。

Sample Input 1

1

2 10

5 1

8 0

Sample Output 1

8

Hint

注，掉頭的時間忽略不計。

題解

這個題的關鍵在于每個人的速度都是一樣的，而且掉頭的時間忽略不計，那麼我們就可以将兩人相遇的情況視作他們從對方身上“穿”了過去，弄明白了這一點，我們就可以将這個題當做求這幾個人與自己初始方向的出口距離的最遠值了。下面看代碼：

#include<stdio.h>
int main()
{
    int T,N,L;
    scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        scanf("%d%d",&N,&L);
        int l [N];
        int m [N];
    int D,z;
        for(int j=0;j<N;j++)
        {
            scanf("%d%d",&D,&z);
            l[j]=D;
            m[j]=z;
        }
        int n [N];
        for(int k=0;k<N;k++)
        {
            if(m[k]==0)
                n[k]=l[k];
            else n[k]=L-l[k];
        }
        int max=n[0];
        for(int o=0;o<N;o++)
        {
            if(n[o]>max)max=n[o];
        }
        printf("%d\n",max);
    }
    return 0;
}
           

代碼的思路就是将輸入的數值求出的距離分别放入一個數組中，再用周遊的方法求出這個數組的最大值。