題意：
給你一個車廂和一些人的位置，這些人都坐在座位上，求這些人全部出去的時間最小值，
注意：
有許多行座位，且每行關于過道對稱，出口在過道一端，一個時間只能移動一個單位，且每時刻每個格子只能有一人
思路：
首先這道題不用演算法，
然后有三個關鍵點：
- 每個人都有各不相同的唯一的一個出車時間，
- 最長出去的時間是最后一個人出去的時間，
- 要想最后一個人盡早出去，人們出去的順序應與初始距離順序相同，
解釋一下第三條：
比如A和B，如果A的距離比B的距離大，那么B一定先到達門口，我們要讓B先出，假設讓A先出，那么B等A來的時候完全可以出去了，等A出去后再出去總時間就是time【A】+1，顯然不如讓B先出去，是time【A】，
方法：
我們將各個人的距離求出并排序，這就是人們的出車順序，但是我們還要處理距離重復的，因為每個人都對應唯一的時間，挨個處理，若他與上一個人的距離相同，就讓他等于上一個人的時間加一，后面同理，答案就是最后一個人的時間，
1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int maxn=500*500*2+3; 8 int Exit,Road,n,dis[maxn]; 9 int main(){ 10 // freopen("1.in","r",stdin); 11 scanf("%d%d%d",&Exit,&Road,&n); 12 Road++;Exit++; 13 int x,y; 14 for(int i=1;i<=n;++i){ 15 scanf("%d%d",&x,&y); 16 if(y>=Road)y++; 17 dis[i]=(Exit-x)+abs(Road-y); 18 } 19 sort(dis+1,dis+1+n); 20 for(int i=2;i<=n;++i){ 21 if(dis[i]<=dis[i-1]){ 22 dis[i]=dis[i-1]+1; 23 } 24 } 25 printf("%d\n",dis[n]); 26 return 0; 27 }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40798.html
標籤：C++
上一篇：Codeforces Round #632 (Div. 2)（A+B）
下一篇：捕獲未經測驗的回傳值