首页 > 代码库 > K-Anonymous Sequence(poj 3709)

K-Anonymous Sequence(poj 3709)

http://poj.org/problem?id=3709

    给定一个长度为n的非严格单调递增数列a1,...,an.每一次操作可以使数列中的任何一项的值减小1。现在要使数列中的每一项都满足其他项中至少有k-1项和它相等。求最少要对这个数列操作的次数。

输入:第一行为测试数据的组数T(1 ≤ T ≤ 20)

   每组测试数据包含两行:

    第一行为两个正整数n,k。n为数列中元素的个数 (2 ≤ n ≤ 500000);

    第二行为非严格单调递增数列的n个整数,正整数的取值范围为[0, 500000]。

输出:

    每组测试数据输出一个正整数,即最少要对这个数列操作的次数。

Sample Input

27 32 2 3 4 4 5 56 20 3 3 4 8 9

Sample Output

35