← 返回题目列表

AtCoder · joisc2021_e

E. 道路建设

中文机器翻译题面 查看原题

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

道路の建設案 (Road Construction) - 原题 PDF 第 1 页
原题PDF第1页
道路の建設案 (Road Construction) - 原题 PDF 第 2 页
原题PDF第2页
道路の建設案 (Road Construction) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 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