2020牛客国庆集训派对day4 Emergency Evacuation

Emergency Evacuation

题意：

有n个人在不同的位置上，在最后面有一个出口exit，所有人都要逃离出去（走出出口），且每个格子最多容纳一个人，当有人挡在前面时，后面的人必须停留，所有人可以同时移动，问最少需要多少步离开

规则：
坐在座位上的乘客可以朝着过道移动到相邻的座位上。靠近过道的座位上的乘客可以侧着身子直接走向过道。

过道上的乘客可以向后移动一排座位。如果乘客在紧急出口前面，也就是最后面的座位排，他/她可以下车

Passengers on a seat can move to an adjacent seat toward the aisle. Passengers on a seat adjacent to the aisle can move sideways directly to the aisle.
Passengers on the aisle can move backward by one row of seats. If the passenger is in front of the emergency exit, that is, by the rear-most seat rows, he/she can get off the car

题解：

一开始想的是如何模拟所有人的行踪，但发现其实没有那么麻烦，如果不存在挡人的情况，那我们可以求出每个人的时间abs(x-r)+abs(y-s)，但是事实是存在挡人的情况，我们可以对每个人的时间进行排序（从大到小），欧几里得距离一样的就会存在挡人情况，我们让欧几里得距离大的先走，相等的给出先后顺序离开，他到出口的欧几里得距离加上他的排名，即（a[i]+i-1）

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[1024769],ans;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int r,s,p;
    cin>>r>>s>>p;
    for(int i=1;i<=p;i++)
    {
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        if(y>=s)y++;
        a[i]=abs(x-r)+abs(y-s);
    }
    sort(a+1,a+1+p,cmp);//从大到小
    for(int i=1;i<=p;i++)
    {
        ans=max(ans,a[i]+i-1);
    }
    cout<<ans;
    return 0;
}