admin管理员组文章数量:1577816
Problem C Emergency Evacuation
Time Limit: 3 seconds
The Japanese government plans to increase the number of inbound tourists to forty million in the year 2020, and sixty million in 2030. Not only increasing touristic appeal but also developing tourism infrastructure further is indispensable to accomplish such numbers.
One possible enhancement on transport is providing cars extremely long and/or wide, carrying many passengers at a time. Too large a car, however, may require too long to evacuate all passengers in an emergency. You are requested to help estimating the time required.
The car is assumed to have the following seat arrangement.
• A center aisle goes straight through the car, directly connecting to the emergency exit door at the rear center of the car. • The rows of the same number of passenger seats are on both sides of the aisle.
A rough estimation requested is based on a simple step-wise model. All passengers are initially on a distinct seat, and they can make one of the following moves in each step.
• 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.
The seat or the aisle position to move to must be empty; either no other passenger is there before the step, or the passenger there empties the seat by moving to another position in the same step. When two or more passengers satisfy the condition for the same position, only one of them can move, keeping the others wait in their original positions.
The leftmost figure of Figure C.1 depicts the seat arrangement of a small car given in Sample Input 1. The car have five rows of seats, two seats each on both sides of the aisle, totaling twenty. The initial positions of seven passengers on board are also shown.
The two other figures of Figure C.1 show possible positions of passengers after the first and the second steps. Passenger movements are indicated by fat arrows. Note that, two of the passengers in the front seat had to wait for a vacancy in the first step, and one in the second row had to wait in the next step.
Your task is to write a program that gives the smallest possible number of steps for all the passengers to get off the car, given the seat arrangement and passengers’ initial positions.
Initial After Step 1 After Step 2
Figure C.1. Simple Model
Input
The input consists of a single test case of the following format.
r s p
i1 j1
. . .
ip jp
Here, r is the number of passenger seat rows, s is the number of seats on each side of the aisle, and p is the number of passengers. They are integers satisfying 1 ≤ r ≤ 500, 1 ≤ s ≤ 500, and 1 ≤ p ≤ 2rs. The following p lines give initial seat positions of the passengers. The k-th line with ik and jk means that the k-th passenger’s seat is in the ik-th seat row and it is the jk-th seat on that row. Here, rows and seats are counted from front to rear and left to right, both starting from one. They satisfy 1 ≤ ik ≤ r and 1 ≤ jk ≤ 2s. Passengers are on distinct seats, that is, ik 6= il or jk 6= jl holds if k 6= l.
Output
The output should be one line containing a single integer, the minimum number of steps required for all the passengers to get off the car.
题意:车厢里有p个人,给出p个人的位置,每个人都要出去,但同时每一时刻只能通过一个人,求全部人出去的 最短时间
思路:下车等于逆向的上车,所以逆向模拟即可,细节看代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[500005];
int cmp(int a,int b){
return a>b;
}
int main(){
int r,s,p;
while(scanf("%d%d%d",&r,&s,&p)!=EOF){
memset(a,0,sizeof(s));
int x=r+1,y=s+1;
for(int i=1;i<=p;i++){
scanf("%d %d",&x,&y);
a[i]+=(r+1-x);
if(y<=s) a[i]+=(s+1-y);
else a[i]+=(y-s);
}
sort(a+1,a+1+p,cmp);///排序离出口越远的排越前;
int cnt=0,ans=-1;
for(int i=1;i<=p;cnt++,i++)
ans=max(ans,a[i]+cnt);
///离出口远的先上车, 那么后面的就要慢一步上车,
///那么有两个人离出口距离相同的话,即a[i]=a[i-1]而且ans=a[i]的话,
///因为cnt比上一次多了一,那么步数就要加一了
printf("%d\n",ans);
}
return 0;
}
本文标签: EmergencyEvacuation
版权声明:本文标题:C - Emergency Evacuation 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1727823317a1131983.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论