ABC 024 C - 民族大移動

問題

問題概要

x軸上をスタートからゴールまで到達するのにかかる最短時間を求める問題。ただし、時間ごとに、動けるx軸上の位置が与えられる。

解法

ループが存在するわけでなく、ただ単にx軸上を動くだけなので、実験すると貪欲にやればいいことがわかる。現在の位置から、目標地点に近づくことができる移動のタイミングがあるなら、いけるところまで毎回近づいていけばいい。このようにしても損することはない。

ミス

なし。

コード

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int n, d, k;
int L[10010], R[10010];
int S[110], T[110];

int main(void){
    cin >> n >> d >> k;
    rep(i, d) cin >> L[i] >> R[i];
    rep(i, k) cin >> S[i] >> T[i];

    rep(i, k){
        int now = S[i];
        rep(j, d){
            if(L[j] <= now && now <= R[j]){
                if(T[i] <= now){
                    now = L[j]; //左に動かせれるだけ動かす  
                    if(now <= T[i]){
                        printf("%d\n", j + 1);
                        break;
                    }
                }
                else{
                    now = R[j];
                    if(now >= T[i]){
                        printf("%d\n", j + 1);
                        break;
                    }
                }
            }
        }
    }
    return 0;
}