ICPC 2018 亚洲横滨赛 C Emergency Evacuation

题目大意

你一个车厢和一些人，这些人都坐在座位上，求这些人全部出去的时间最小值

Solution

题目咋说就咋做

直接模拟

我们考虑每个人的路线，如果这两个人在没有阻挡的情况下，到达终点的时间是一样的话，那么必定会在某一点相遇。

此时就需要有一个人要等一个时刻，如果有第三个人的话，这第三个就要等两个时刻，那么我们直接算出每个人到终点的时间，排序后依次后延即可。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

struct node{

  int r, c;

  int d;

}pe[500005];

bool cmp(node a, node b){

    return a.d > b.d;

}

int main(){

    int r, s, p, i;

    cin >> r >> s >> p;

    for(i = 0; i < p; i++){

        cin >> pe[i].r >> pe[i].c;

        if(pe[i].c > s)

            pe[i].d = (pe[i].c - s) + (r - pe[i].r + 1);

        else

            pe[i].d = (s - pe[i].c + 1) + (r - pe[i].r + 1);

    }

    sort(pe, pe + p, cmp);

    int k = 1;

    int ans = pe[0].d;

    for(i = 1; i < p; i++){

        if(pe[i].d + k > ans)

            ans = pe[i].d + k;

        k++;

    }

    cout << ans << endl;

    return 0;

}

巴特西

ICPC 2018 亚洲横滨赛 C Emergency Evacuation（暴力，贪心）

ICPC 2018 亚洲横滨赛 C Emergency Evacuation

题目大意

Solution

最新文章

热门文章