Codeforces 967 C problem solving Report

Topic 1

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

Two, train of thought

(1) If it's on the same floor, go straight to it without climbing the stairs or taking the elevator.
(2) If it is on different floors, calculate the time spent climbing stairs and taking the elevator respectively, and take the minimum value.
(1) When calculating the time to climb a stair, if there is only one stair next to the starting room, calculate the time required to pass the stair from the starting room to the ending room.
If there are two or more stairs next to the starting room, the time required to climb from the two stairs on the left and right nearest to the starting room number to the ending room shall be calculated respectively, and then the minimum value shall be taken.
(2) The elevator is the same as the stairs.
(3) From the results of (1) and (2), take the minimum value.

Three, code

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

int main()
{
    int n, m, c1, c2, v; //Number of floors, section number of each floor, number of stairs, number of elevators, and the number of floors that the elevator can rise and fall per unit time
    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; //Query several times, the floor number and room number of the starting room, the floor number and room number of the target room
    int updownPos; //Location of stairs or elevators
    scanf("%d", &q);
    while(q--)
    {
        int ans=1000000000, k; //k is the number of stairs or elevators
        scanf("%d %d %d %d", &floor1, &room1, &floor2, &room2);

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

        //Choose the stairs to climb by binary search method
        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));
        }

        //Choose which elevator to take with binary search method
        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 communication QQ group: 648202993
More content, please pay attention to WeChat official account.


wechat_public.jpg

Posted on Sat, 28 Mar 2020 08:13:09 -0700 by AGISB