以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 2 – Road Construction
道路の建設案(Road Construction)
JOI 国にはN 個の町があり,1 からN までの番号が付けられている.JOI 国の国土は座標平面とみなせ
る.町i (1 ≦i ≦N) の座標は(Xi, Yi) である.
JOI 国では町と町をつなぐ道路をK 本建設する予定である.町i と町j (i , j) をつなぐ道路の建設には
|Xi −Xj| + |Yi −Yj| 円かかる.ただし,町i と町j をつなぐ道路の建設と町j と町i をつなぐ道路の建設は同
じものとみなす.
建設担当者であるあなたは,建設費用を見積もるために,いくつかの町の組合せに対して費用を算出する
ことにした.道路を建設する町の組合せはN(N −1) 通り存在するが,そのうち安い方からK 個の費用を
2
知りたい.
JOI 国の町の座標とK の値が与えられたとき,安い方からK 個の建設費用を計算するプログラムを作成
せよ.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N K
X1 Y1
...
XN YN
出力
標準出力にK 行で出力せよ.k 行目(1 ≦k ≦K) にはk 番目に安い道路の建設費用を出力せよ.
制約
• 2 ≦N ≦250 000. ( )
N(N −1)
• 1 ≦K ≦min 250 000, .
2
• −1 000 000 000 ≦Xi ≦1 000 000 000 (1 ≦i ≦N).
• −1 000 000 000 ≦Yi ≦1 000 000 000 (1 ≦i ≦N).
• (Xi, Yi) , (Xj, Yj) (1 ≦i < j ≦N).
道路の建設案– 1 / 3
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 2 – Road Construction
小課題
1. (5 点) N ≦1 000.
2. (6 点) Yi = 0 (1 ≦i ≦N).
3. (7 点) K = 1.
4. (20 点) K ≦10.
5. (27 点) N ≦100 000.
6. (35 点) 追加の制約はない.
入出力例
入力例1 出力例1
3 2 1
-1 0 2
0 2
0 0
町1 の座標は(−1, 0),町2 の座標は(0, 2),町3 の座標は(0, 0) である.
町の組合せは以下の3 × 2 = 3 通りある.
2
• 町1 と町2 をつなぐ道路を建設した場合,|(−1) −0| + |0 −2| = 3 円かかる.
• 町1 と町3 をつなぐ道路を建設した場合,|(−1) −0| + |0 −0| = 1 円かかる.
• 町2 と町3 をつなぐ道路を建設した場合,|0 −0| + |2 −0| = 2 円かかる.
これらを安い順に並べると1, 2, 3 となるので,1 行目に1 を,2 行目に2 を出力する.
この入力例は小課題1, 4, 5, 6 の制約を満たす.
道路の建設案– 2 / 3
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 2 – Road Construction
入力例2 出力例2
5 4 2
1 -1 2
2 0 3
-1 0 3
0 2
0 -2
N = 5 なので,町の組合せは5 × 4 = 10 通りある.
2
建設費用を安い順に並べると2, 2, 3, 3, 3, 3, 4, 4, 4, 4 となる.安い方から4 個の費用は2, 2, 3, 3 である.
この入力例は小課題1, 4, 5, 6 の制約を満たす.
入力例3 出力例3
4 6 1
0 0 1
1 0 2
3 0 3
4 0 3
4
この入力例は小課題1, 2, 4, 5, 6 の制約を満たす.
入力例4 出力例4
10 10 3
10 -8 3
7 2 4
7 -8 5
-3 -6 6
-2 1 6
-8 6 6
8 -1 7
2 4 7
6 -6 7
2 -1
この入力例は小課題1, 4, 5, 6 の制約を満たす.
道路の建設案– 3 / 3