Codeforces 967 C 題解報告

一、題目

​​http://codeforces.com/contest/967/problem/C​​

二、思路

（一）如果是同一樓層，則直接走過去，不用爬樓梯也不用乘電梯。

（二）如果是不同樓層，分别計算爬樓梯和乘電梯所用的時間，取最小值。

（1）在計算爬樓梯所用時間時，若起始房間旁邊隻有一個樓梯，計算從起始房間經過該樓梯到達終點房間所需的時間。

若起始房間旁邊有兩個或更多的樓梯，要分别計算從離起始房間号最近的左右兩邊的兩個樓梯爬上去到達終點房間所需的時間，再取最小值。

（2）乘電梯的道理與爬樓梯的道理一樣。

（3）從（1）和（2）的結果中，取最小值。

三、代碼

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

int main()
{
    int n, m, c1, c2, v; //層數，每層section數，樓梯數，電梯數，電梯每機關時間能升降的層數
    scanf("%d %d %d %d %d", &n, &m, &c1, &c2, &v);

    int a[c1], b[c2];
    for(int i = 0; i < c1; i++)
    {
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < c2; i++)
    {
        scanf("%d", &b[i]);
    }

    int q, floor1, room1, floor2, room2; //查詢幾次，起始房間的層号和房間号，目标房間的層号和房間号
    int updownPos; //樓梯或電梯的位置
    scanf("%d", &q);
    while(q--)
    {
        int ans=1000000000, k; //k表示第幾個樓梯或電梯
        scanf("%d %d %d %d", &floor1, &room1, &floor2, &room2);

        if(floor1 == floor2)
        {
            printf("%d\n", abs(room2 - room1));
            continue;
        }

        //爬樓梯，用二分查找法選擇爬第幾個樓梯
        k = lower_bound(a, a + c1, room1) - a;  
        if(k < c1)
        {
            updownPos = a[k];
            ans = min(ans, abs(updownPos - room1) + abs(floor2 - floor1) + abs(room2 - updownPos));
        }
        if(k > 0)
        {
            updownPos = a[k-1];
            ans = min(ans, abs(updownPos - room1) + abs(floor2 - floor1) + abs(room2 - updownPos));
        }

        //乘電梯，用二分查找法選擇乘哪個電梯
        k = lower_bound(b, b + c2, room1) - b;
        if(k < c2)
        {
            updownPos = b[k];
            ans = min(ans, abs(updownPos - room1) + (abs(floor2 - floor1) + v - 1) / v + abs(room2 - updownPos));
        }

        if(k > 0)
        {
            updownPos = b[k - 1];
            ans = min(ans, abs(updownPos - room1) + (abs(floor2 - floor1) + v - 1) / v + abs(room2 - updownPos));
        }

        printf("%d\n", ans);
    }
    return 0;
}      

TopCoder & Codeforces & AtCoder交流QQ群：648202993

更多内容請關注微信公衆号