P2541 [USACO16DEC] Robotic Cow Herd P 题解

· · 题解

题目大意

题目抽象成一个 n 行 k 列的表格，对于每行只有固定几个值可选，在满足每列互不相同的情况下，求表格中所有值和的最小值。

题目分析

我们不妨将答案表格排个序，很容易发现最小一列一定是所有行最小值组成的，然后我们来考虑第二小的列，简单思考可得，这一列一定是第一列其中一个值替换成另一个值所得。

我们将这一结论推广，我们设一列为一个状态，通过这一列我们将其中任意一个值改为比这个值大的那个值就可以直接得到另一个比这个状态稍大的状态，由此我们可以得到所有状态。

然后我们可以以最小状态为基础，衍生其他状态，找到最小的 k 个状态，我们只需用一个优先队列维护即可。

然后时间复杂度就是 \mathcal O(k \times n \log n)。

很明显过不了，我们发现时间复杂度较大的原因是对于每个状态，我们都会派生出 n 个状态，并且不同状态可能会派生出相同的状态，这样就会重复计算。

为优化算法，我们可以考虑更改派生方法使之不会重复，从而优化这一部分的时间。

我们发现对于所有状态，我们都可以找到一个点 p_{x,y}，使得 x 之下都是当前行的最小值。

我们考虑对于 p 做点文章，我们只需派生 3 种状态：

  1. 将 p 向右一列，即 p_{x, y} \to p'_{x, y+1}

  2. 将 p 向下一行，即 p_{x, y} \to p'_{x+1, y}

  3. 当 y = 2，p 向左一行，同时下一行的点向右一列。

非常巧妙的方法，同样也可以派生所有的状态，不过说实话非常难想。

时间复杂度是 \mathcal O(k \log n) 加上一个小常数的。

code

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#define int long long

using namespace std;

const int N = 1e5 + 5, INF = 2e18;
struct cow{
    int len, d[20], val;
}p[N];
struct node{
    int val, x, y;
};
int n, k, ans;
priority_queue <node> q;

bool cmp(int x, int y){return x < y;}
bool cmp_val(cow x, cow y){return x.val < y.val;}
bool operator < (node u, node v){return u.val > v.val;}

signed main()
{
    scanf("%lld %lld", &n, &k);
    for(int i = 1;i <= n;i++)
    {
        scanf("%lld", &p[i].len);
        for(int j = 1;j <= p[i].len;j++)
            scanf("%lld", &p[i].d[j]);
        p[i].d[p[i].len+1] = INF;
        sort(p[i].d + 1, p[i].d + p[i].len + 1, cmp);
        p[i].val = p[i].d[2] - p[i].d[1];
        ans += p[i].d[1];
    }
    sort(p + 1, p + n + 1, cmp_val);
    q.push({ans - p[1].d[1] + p[1].d[2], 1, 2});
    for(int i = 1;i < k;i++)
    {
        node u = q.top();
        q.pop();
        ans += u.val;
        q.push({u.val - p[u.x].d[u.y] + p[u.x].d[u.y+1], u.x, u.y+1});
        if(u.x != n)
            q.push({u.val - p[u.x+1].d[1] + p[u.x+1].d[2], u.x+1, 2});
        if(u.x != n && u.y == 2)
            q.push({u.val - p[u.x+1].d[1] + p[u.x+1].d[2] - p[u.x].d[2] + p[u.x].d[1], u.x+1, 2});
    }
    printf("%lld", ans);
    return 0;
}