#D0315. 隔岸观火

隔岸观火

题目背景

阳乖序乱,阴以待逆。暴戾恣睢,其势自毙。顺以动豫,豫顺以动。

题目描述

33DAI 在一条路边有 nn 个仓库。从左到右分别编号为 1n1\sim n。为了避免着火,33DAI 准备安排 kk 只小猫站岗监视。每只小猫的站岗位置都只能是某个仓库(允许多只猫在同一个仓库)。

当一个仓库着火时,离仓库最近的小猫就会赶往仓库救火,这需要花费小猫到仓库的距离那么多救火时间。比如仓库 55 着火时,如果仓库 1313 的小猫离他最近,那么就需要 135=813-5=8 的救火时间。

请你给这 kk 只小猫分别分配一个仓库,使得最大救火时间尽可能的少(显然你分配好小猫后,每个仓库着火都可以算出一个救火时间,最大救火时间即所有这些救火时间中的最大值)。

如果有多种方案,输出任意一种都可以。

输入格式

空格隔开的两个整数 n,kn,k

输出格式

输出 kk 行,每行一个整数,即你安排的每只小猫驻守仓库。

5 3
2
4
5

此时,仓库 151\sim 5 的救火时间分别为:1,0,1,0,01,0,1,0,0,最大救火时间为 11

显然这只是一个方案,1,3,51,3,52,4,42,4,42,2,42,2,4 等都是合法的方案。

100 1
51

显然 5050 也是一个合法方案。

100 2
76
25

此时救火时间最久的是 50(5025=25)50(50-25=25)51(7651=25)51(76-51=25)。当然还有其他安排小猫的方案。比如 26,7726,77

201 3
34
101
168

这三个位置的其他排列顺序都可以。但不可能有其他数组成的答案。此时救火时间最大的几个城市分别是 1,67,68,134,135,2011,67,68,134,135,201。他们的救火时间都是 3333

数据规模与约定

对于 100%100\% 的数据,1kn2×1061 \le k\le n \le 2\times 10^6

  • 子任务 1(10 分):保证 k=nk=n
  • 子任务 2(20 分):保证 k=1k=1
  • 子任务 3(30 分):保证 k100k\le 100
  • 子任务 4(40 分):没有特殊限制。