先看这篇题解理解整体的思路
看完后非常有感觉, 但是当写到函数时候发现根据这个思路直接写的话和暴力没啥区别, 所以又陷入了沉思hh
那么这个时候就得谈到多路归并了, 所以返回刚才那个题解再仔细看一遍, 得到每次只需要改变一个数字即可.
这样就可以很快的得到解决暴力做的问题, 下一步就是写代码, 写java
的同学看到y总的代码估计一般人都傻了
可以参考一下我的代码hh, 下面有一个进阶版的代码
ac代码
import java.util.*;
public class Main {
static int N = 2010, n, m;
static int[] p = new int[N];
static int[] h = new int[N];
static int[] res = new int[N]; // 结果数组
public static void solve()
{
Queue<PII> q = new PriorityQueue<>();
for (int i = 1; i <= n; i ++ )
q.add(new PII(h[1] + p[i], 1, i));
int cnt = 1;
while (cnt <= n)
{
PII t = q.poll();
int a = t.a; // 当前值
int b = t.b; // 表示h数组下标
int c = t.c; // p数组的下标
res[cnt ++] = a;
q.add(new PII(h[b + 1] + p[c], b + 1, c)); // 这里可以发现这个p数组的下标是不用变的
// 如果想不清楚为啥可以再去想多路归并其实有一个数组的值是不用变的, 这样就有了下面进阶版的代码
}
for (int i = 1; i <= n; i ++ )
h[i] = res[i];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int C = 1; C <= T; C ++ )
{
Arrays.fill(h, 0);
m = sc.nextInt(); n = sc.nextInt();
for (int i = 1; i <= n; i ++ )
h[i] = sc.nextInt();
Arrays.sort(h, 1, n + 1);
for (int i = 1; i < m; i ++ )
{
for (int j = 1; j <= n; j ++ )
p[j] = sc.nextInt();
Arrays.sort(p, 1, n + 1);
solve();
}
for (int i = 1; i <= n; i ++ )
System.out.print(h[i] + " ");
System.out.println();
}
}
}
class PII implements Comparable<PII>
{
int a; // 值为多少
int b; // h数组的下标
int c; // p数组的下标
public PII(int a, int b, int c)
{
this.a = a;
this.b = b;
this.c = c;
}
public int compareTo(PII o)
{
return this.a - o.a;
}
}
之后说一下自己的错误hh
刚开始想的是通过指针的方式去记录最小值
public static void solve()
{
h = Arrays.copyOf(res, N);
int cnt = 1;
int l = 2, r = 1, cul = 1, cur = 1;
while (cnt <= n)
{
if (h[l] != 0 && h[l] + p[r] < h[cul] + p[cur])
{
res[cnt ++] = h[l] + p[r];
cul = l; cur = r;
l ++;
}
else
res[cnt ++] = h[cul] + p[cur ++];
}
}
这样的话可能中间存在p[1] + h[k]
是小于p[m] + h[1]
的
这样写代码就取不到前者, 但后者可能会取到, 这样会让结果出现错误