2018-2019|2018-2019, ICPC, Asia Yokohama Regional Contest 2018 C、Emergency Evacuation(逆向思维)
C Emergency Evacuation
题意： 【2018-2019|2018-2019, ICPC, Asia Yokohama Regional Contest 2018 C、Emergency Evacuation(逆向思维)】输入 r , s ( 500 ) , p ( 2 × r × s ) r,s(500),p(2\times r\times s) r,s(500),p(2×r×s)表示由 r r r行座位，每行有两边，每边 s s s列。
有 p p p个乘客，接下来给出它们的位置，问乘客下车最少需要多少时间。
文章图片
题解： 从乘客下车来考虑，不太好做。
不妨从反方向思考，乘客上车，乘客上车最少时间肯定是距离座位远的乘客先上车最优了。
代码：
#include
using namespace std;
typedef long long ll;
const int N=5e6+9;
int r,s,n;
struct T{
int x,y;
}a[N];
ll mx;
bool cmp(T t1,T t2){
return t1.x+t1.y>t2.x+t2.y;
}
int main(){
cin>>r>>s>>n;
for(int i=1;
i<=n;
i++){
cin>>a[i].x>>a[i].y;
a[i].x=r-a[i].x;
if(a[i].y<=s)a[i].y=s-a[i].y+1;
else a[i].y-=s;
}
sort(a+1,a+n+1,cmp);
for(int i=1;
i<=n;
i++)mx=max(mx,1ll*i+a[i].x+a[i].y);
cout<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 2018-2019|2018-2019, ICPC, Asia Yokohama Regional Contest 2018 K
- ---------Online|HDU 5528 Count a*b ACM/ICPC 2015 Changchun（数论）