专做毕业设计的网站,asp网站建设教程,c# 网站开发框架,可以做试卷的网站英语怎么说Emergency Evacuation
题意#xff1a;
有n个人在不同的位置上#xff0c;在最后面有一个出口exit#xff0c;所有人都要逃离出去#xff08;走出出口#xff09;#xff0c;且每个格子最多容纳一个人#xff0c;当有人挡在前面时#xff0c;后面的人必须停留#x…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
代码
#includeiostream
#includecstdio
#includealgorithm
#includecmath
using namespace std;
int a[1024769],ans;
bool cmp(int a,int b)
{return ab;
}
int main()
{int r,s,p;cinrsp;for(int i1;ip;i){int x,y;cinxy;x--;y--;if(ys)y;a[i]abs(x-r)abs(y-s);}sort(a1,a1p,cmp);//从大到小for(int i1;ip;i){ansmax(ans,a[i]i-1);}coutans;return 0;
}
