POJ2442:Sequence 题解

思路与神奇操作

这道题我们首先会不可避免地对每一个序列进行排序。每一个序列的顶部的和就是最大和,而次大和就是 \(n-1\)个序列的最大和一个头部值最小的序列的头部值 之和。所以,我们把视野缩小一些,讨论两个序列的合并。

两个区间的最优解一定是\(a[1]与b[1]\),当然这两个序列已经排过序了。那么次优解就是\(max\{a[1]+b[2],a[2]+b[1]\}\)。我们可以从一个最优解分裂出两个候选项。但是我们发现,如果将这个进行到第三步时,就会出一些奇奇怪怪的问题。

第三步:次次优解是\(max\{a[2]+b[2],a[2]+b[2],a[1]+b[3],a[3]+b[1]\}\),我们发现会有两个项重复,而且在比较中只能比较两个项,所以很容易出现重复的情况。我们在这里就可以使用标题中提到的神奇操作:我们定义一个 ADT 来储存我们每个解在两个序列的偏移量和解的值,并且还要定义一个\(flag\)的布尔变量,来进行区分。因为重叠解的出现是有一定周期的(周期长度就是2次操作),所以每一次操作时碰见\(flag==true\),就少添加一个解。如果碰上\(flag==false\),那就果断把一个解派生成两个解。

具体的可以看看代码:

// POJ2442.cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
int T, m, n, seq[110][2020], seqb[2020], tmp[2020];
struct node
{
    int val, l, r;
    bool flag;
    bool operator<(const node &nd) const
    {
        return val > nd.val;
    }
};

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &m, &n);
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
                scanf("%d", &seq[i][j]);
            sort(seq[i] + 1, seq[i] + n + 1);
        }
        for (int i = 1; i <= n; i++)
            seqb[i] = seq[1][i];
        for (int ln = 2; ln <= m; ln++)
        {
            priority_queue<node> npool;
            npool.push(node{seqb[1] + seq[ln][1], 1, 1, false});
            int cnt = 1;
            while (cnt <= n)
            {
                node curt = npool.top();
                npool.pop();
                tmp[cnt++] = curt.val;
                if (!curt.flag)
                    npool.push(node{seqb[curt.l + 1] + seq[ln][curt.r], curt.l + 1, curt.r, false});
                npool.push(node{seqb[curt.l] + seq[ln][curt.r + 1], curt.l, curt.r + 1, true});
            }
            for (int i = 1; i <= n; i++)
                seqb[i] = tmp[i];
        }
        for (int i = 1; i <= n; i++)
            printf("%d ", seqb[i]);
        printf("\n");
    }
    return 0;
}

 

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注