TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1181
  • 問題
  • P1181【IOI 2000】邮局问题
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    一些村庄建在一条笔直的高速公路边上,我们用一条坐标轴来描述这条公路,每个村庄的坐标都是整数,没有两个村庄的坐标相同。两个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用与它距离最近的邮局,建立邮局的原则是:所有村庄到各自使用的邮局的距离总和最小。
    数据规模:1<=村庄数<=300, 1<=邮局数<=30, 1<=村庄坐标<=10000

    入力形式

    2行

    第一行:n m {表示有n个村庄,建立m个邮局}
    第二行:a1 a2 a3 .. an {表示n个村庄的坐标}

    出力形式

    1行

    第一行:l {l表示最小距离总和}

    サンプル入力

    10 5
    1 2 3 6 7 9 11 22 44 50

    サンプル出力

    9


    ソース  IOI2000' 第五题