UVA 11997 K Smallest Sums

UVA_11997

    由于K行处理起来比较繁琐，所以一个可行的思路是就当作两行处理，这样处理K-1次就可以了。

    对于只有两行的情况，可以考虑怎样才能够一个一个的将和由小到大构造出来，这一点可以借助优先级队列来实现：先将两个最小的放进去，之后每次都取出和最小的那两个数，然后尝试将第一个数换成第一行的稍大一点的数后放到优先级队列中，然后再尝试将第二个数换成第二行稍大一点的数放到优先级队列中。这样从优先级队列中取出的前K个元素就是前K小的和。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define minD 562510
#define minK 760
#define INF 0x3f3f3f3f
int N, D, min[4 * minD], a[minK][minK], ans[minK];
void init()
{
    int i, j;
    for(i = 0; i < N; i ++)
    {
        for(j = 0; j < N; j ++) scanf("%d", &a[i][j]);
        std::sort(a[i], a[i] + N);    
    }
    for(D = 1; D < N * N + 2; D <<= 1);
    memset(min, 0x3f, sizeof(min[0]) * 2 * D);
}
void update(int i)
{
    for(; i ^ 1; i >>= 1)
        min[i >> 1] = std::min(min[i], min[i ^ 1]);    
}
int getid()
{
    int i;
    for(i = 1; i < D;)
    {
        if(min[i << 1] == min[i]) i <<= 1;
        else i = i << 1 | 1;    
    }
    return i;    
}
void pop()
{
    int i = getid();
    min[i] = INF, update(i);
}
void push(int x, int y, int v)
{
    int i = x * N + y;
    min[D + i] = v, update(D + i);
}
void top(int &x, int &y, int &v)
{
    int i = getid() - D;
    x = i / N, y = i % N, v = min[D + i];
}
void solve()
{
    int i, j, x, y, v, cnt;
    for(i = 1; i < N; i ++)
    {
        while(min[1] != INF) pop();
        cnt = 0;
        push(0, 0, a[i - 1][0] + a[i][0]);
        while(cnt < N)
        {
            top(x, y, v), pop();
            ans[cnt ++] = v;
            if(x < N) push(x + 1, y, a[i - 1][x + 1] + a[i][y]);
            if(y < N) push(x, y + 1, a[i - 1][x] + a[i][y + 1]);
        }
        for(j = 0; j < N; j ++) a[i][j] = ans[j];
    }
    printf("%d", a[N - 1][0]);
    for(i = 1; i < N; i ++) printf(" %d", a[N - 1][i]);
    printf("\n");
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        init();
        solve();
    }
    return 0;    
}