AtCoder Beginner Contest #057 B問題 - Checkpoints

Source

AtCoder Beginner Contest #057
問題文

問題概要

2次元平面の格子点に $N$ 人の人がいて，人 $i$ は座標 $(A_i, B_i)$ にいる．
チェックポイントが同様に格子点に $M$ 個あり，チェックポイント $j$ の座標は $(C_j, D_j)$ である．
各々の人はマンハッタン距離で最も近いチェックポイントに移動する．
最も近いチェックポイントが複数ある場合は，その中で番号の一番小さいチェックポイントに移動する．
各々の人が何番のチェックポイントに移動するかを求める問題．
座標 $(x_1, y_1)$ と $(x_2, y_2)$ とのマンハッタン距離は $|x_1-x_2| + |y_1-y_2|$ で定義される．

解法

やるだけ．

cLay（version 20170330-1）のコード

C++に変換後のコードはこちら

int N, M, A[50], B[50], C[50], D[50];
{
  int i, j, tmp, mn, res;
  rd(N, M, (A,B)(N), (C,D)(M));

  rep(i,N){
    mn = int_inf;
    rep(j,M){
      tmp = abs(A[i]-C[j]) + abs(B[i]-D[j]);
      if(mn > tmp) mn = tmp, res = j;
    }
    wt(res+1);
  }
}

Current time: 2024年04月27日07時01分08秒
Last modified: 2017年04月01日02時26分04秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC057 ABC_B
トップページに戻る

Logged in as: unknown user (not login)

ログイン：