Submission #60693

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <limits>
using namespace std;
signed main()
{
int N, Q;
cin >> N >> Q;
// x, y の入力
int x[N], y[N];
for(int i = 0; i < N; ++i){
cin >> x[i] >> y[i];
}
// (now_,now_y)：現在いる交差点
// sum：通った道路の本数
int now_x = 1, now_y = 1;
int64_t sum = 0;
for(int i = 0; i < Q; ++i){
// count：距離がkに最も近い観光スポットの個数
// (min_x,min_y)：距離が最もkに近い観光スポットのある交差点
// min_dist：(min_x,min_y)への距離とkとの差の絶対値(この値が小さいほどkに近い),初期値はとても大きい値にしておく
int64_t k, min_dist = 20000000000;
int count = 0, min_x, min_y;
cin >> k;
// 全ての観光スポットを見て、最も距離がkに近い観光スポットを探す
for(int j = 0; j < N; ++j){
// 今いる観光スポットは見ない(距離が1以上を満たさないため)
if(!(x[j] == now_x && y[j] == now_y)){
// j番目の観光スポット方への距離が、現在最小としているmin_distの値よりも小さい場合
// abs(k - abs(now_x - x[j]) + abs(now_y - y[j]))：(x[j],y[j])への距離とkとの差の絶対値
if(min_dist > abs(k - (abs(now_x - x[j]) + abs(now_y - y[j])))){
count = 1;
min_dist = abs(k - (abs(now_x - x[j]) + abs(now_y - y[j])));
min_x = x[j];
min_y = y[j];
// j番目観光スポットへの距離が、min_distと等しい場合(距離が最小の観光スポットが複数ある場合)
}else if(min_dist == abs(k - (abs(now_x - x[j]) + abs(now_y - y[j])))){
++count;
}
}
}
// 距離がkに近い観光スポットが一つの場合
if(count == 1){
sum += abs(now_x - min_x) + abs(now_y - min_y);
now_x = min_x;
now_y = min_y;
// 距離がkに近い観光スポットが複数ある場合
}else{
sum += abs(now_x - 1) + abs(now_y - 1);
now_x = 1;
now_y = 1;
}
}
cout << sum << '\n';
return (0);
}

ステータス

項目 データ
問題 1354 - 山田之国
ユーザー名 ei1903
投稿日時 2020-07-12 22:38:46
言語 C++17
状態 Accepted
得点 50
ソースコード長 2426 Byte
最大実行時間 32 ms
最大メモリ使用量 724 KB

セット

セット 得点 Cases
1 ALL 50 / 50 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 32 ms 604 KB
1
in02.txt AC 23 ms 700 KB
1
in03.txt AC 20 ms 668 KB
1
in04.txt AC 24 ms 508 KB
1
in05.txt AC 22 ms 480 KB
1
in06.txt AC 27 ms 584 KB
1
in07.txt AC 25 ms 552 KB
1
in08.txt AC 20 ms 652 KB
1
in09.txt AC 24 ms 488 KB
1
in10.txt AC 20 ms 588 KB
1
in11.txt AC 19 ms 560 KB
1
in12.txt AC 22 ms 536 KB
1
in13.txt AC 24 ms 628 KB
1
in14.txt AC 20 ms 724 KB
1
in15.txt AC 19 ms 692 KB
1
in16.txt AC 19 ms 664 KB
1
in17.txt AC 30 ms 632 KB
1
in18.txt AC 25 ms 608 KB
1
in19.txt AC 18 ms 576 KB
1
in20.txt AC 20 ms 676 KB
1
in21.txt AC 19 ms 520 KB
1
sample01.txt AC 19 ms 620 KB
1
sample02.txt AC 19 ms 588 KB
1