ABC024: C - 民族大移動

問題

C: 民族大移動 - AtCoder Beginner Contest 024 | AtCoder

個ノードが存在する。種類の民族がそれぞれのノードに居る。 日間以内に、各民族がまで移動する。 日目にはからまでのノードを行き来できる。 各民族について、最短日数を出力せよ。 すべての民族は日以内に到達できることが保証されている。

• 
• 
• 
• 
• 

解答

街を数直線状に並べて考える。 日目に各民族について、目標に向かって右または左に貪欲的に移動させる。 日のシミュレーションで解が求まるので、で解ける。

int main() {
  int N, D, K; cin >> N >> D >> K;
  int L[D], R[D];
  rep (i, D) {
    cin >> L[i] >> R[i];
  }
  int S[K], T[K];
  rep (i, K) {
    cin >> S[i] >> T[i];
  }

  int ans[K];
  rep (i, K) ans[i] = -1;

  rep (i, D) {
    rep (j, K) {
      if (S[j] <= T[j]) {
        if (L[i] <= S[j] && S[j] <= R[i]) {
          S[j] = R[i];
        }
        if (ans[j] == -1 && T[j] <= S[j]) {
          ans[j] = i + 1;
        }
      } else {
        if (L[i] <= S[j] && S[j] <= R[i]) {
          S[j] = L[i];
        }
        if (ans[j] == -1 && S[j] <= T[j]) {
          ans[j] = i + 1;
        }
      }
    }
  }

  rep (i, K) {
    std::cout << ans[i] << "\n";
  }
  
  return 0;
}