P3599.第3题-最小化数组
题目内容
给定一个长度为 n 的数组 {a1,a2,…,an}，以及一个整数 m ，保证 m 是 n 的因子 (即 m∣n )，你可以进行如下操作任意次：
- 选择两个不同的下标 i,j ，满足 i mod m=j mod m ，交换 ai 与 aj 。
请最小化如下目标函数：
∑r=1n/mmax(a(r−1)m+1,a(r−1)m+2,...,a(r−1)m+m)
井输出一种使该和值最小化后的数组。若存在多种最优方案，可以输出任意一种最优方案。
【名词解释】
- 取模：x mod m 表示 x 除以 m 的余数。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数 T(1≦T≦104) 代表数据组数，每组测试数据描述如下：
第一行输入两个整数 n,m(l≦n≦2×105;1≦m≦n;m∣n) 。
第二行输入 n 个整数 a1,a2,…,an(1≦ai≤109) 表示数组元素。
除此之外，保证单个测试文件的 n 之和不超过 2×105 。
输出描述
对于每一组测试数据，新起一行，输出 n 个参数，表示在允许操作后、使目标函数取到最小值时的数组。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
样例1
输入
2
6 3
4 1 5 2 3 6
8 2
7 1 6 2 5 3 4 8
输出
2 1 5 4 3 6
4 1 5 2 6 3 7 8
说明
在第一组样例中：答案为
max(a1,a2,a3)+max(a4,a5,a6)=max(2,1,5)+max(4,3,6)=5+6=11 。
可以证明此时答案最小。
样例2
输入
1
4 4
10 20 30 40
输出
10 20 30 40
