本题关联比赛
20161114

关于社长的qwa 的近10条评论(全部评论)
回复 @Tabing : %%% Smile 2016-11-15 18:29 3楼
Tabing010102 2016-11-14 19:37 2楼
我即使是死了,钉在棺材里了,也要在墓里,用这腐朽的声带喊出：“垃圾OI，毁我青春。” 最长上升子序列 2016-11-14 18:58 1楼

2544. 社长的qwa

★ 输入文件：qwa.in 输出文件：qwa.out 简单对比
时间限制：1 s 内存限制：256 MiB

Opah很难Q中人，于是她决定主W。W是范围伤害，可以给予一个区间内敌人伤害。

Opah一共有n名敌人，她的敌人们站在一根数轴上。

Opah的W可以给予k个不同的敌人伤害，所以说她希望找到k名数轴上的敌人，使任意无序二元敌人对$(x_i,x_j)$的距离之和最小，即$$\sum_{1\leq i\leq j\leq n}|x_i - x_j|$$最小

第一行有两个被空格隔开的正整数，分别为$n$($n<=10^5$)和$k(k<=n)$

第二行有n个被空格隔开的数，表示每一名敌人的坐标($|x_i|<2^{30}$)

（保证没有两名敌人在同一位置）

一个整数ans,表示最小距离和

4 3 1 2 3 8

选1,2,3，这三个点。

|1-2|+|1-3|+|2-3|=4

对于100%的数据, $1<= n <= 10^5$

30%: $n <= 10^2$

30%: $n <= 10^3$

20%: $n <= 10^4$

20%: $n <= 10^5$

Ra~piz！