1 条题解

  • 1
    @ 2024-12-24 10:31:35

    仓库货物调配问题

    tag

    贪心,枚举,数据结构

    题意简述

    给定一个 n×mn \times m 的矩阵,每次操作可以选择一列或者一行,将这一列数的和计入收益,然后将这一列数全部减少 pp。求操作 kk 次的最大收益。

    fun fact

    赛时看到这个题的时候,注意到每次取行和列都互相不影响(应该说,假设取走某一行后,相当于再每一列都取走了一个固定的 pp,不影响每一列和的相对大小)。所以想到一个贪心策略:每次取和最大的行或者列。这样很容易实现,利用2个优先队列维护行和列的和,每次去除两个对头比较,取较大的取出,取出后(假设取出的是行),将他减去 m×pm \times p 后再加入优先队列,然后再给列的tag加上 pp(表示给所有列都减去了一个 pp),这样就可以保证每次取的都是当前最大的行或者列。

    事实上,这个思路是错误的,或者说不好处理这种情况:存在行最大值和列最大值相同的情况。比如样例:

    input1:
    3 3 2 4
    5 4 3
    5 4 4
    1 2 6
    ans1:
    25
    
    input2:
    3 3 2 4
    5 5 1
    4 4 2
    3 4 6
    ans2:
    25
    

    在第一个样例中应该先取行,而第二个中应该先取列。

    题解思路

    回到正确的思路,我们还是有结论:取行和列互不影响。我们错误的贪心在于无法处理行和列相等时,应该先取行还是先取列。我们跳过这个问题,既然行和列互不影响,我们考虑答案的结构:答案一定是取 xx 次行最大和 yy 次列最大。那么很显然,xxyy 是我们可以枚举的,而取 xx 次行最大和 yy 次列最大,这是我们可以先行预处理出来的,再做前缀和即可。然后枚举 xx,那么 y=kxy = k - x,每次的答案就是 f(x)=prerowx+precolkxf(x) = pre_{row_x} + pre_{col_{k-x}}。但是,我们还需要考虑行和列会有交叉操作:假设我们取了 xx 次行,那么每一列的值都应该相应的减少 x×px \times p,所以我们取 kxk - x 次列时,这一部分是多计算的(也就是把 x×px \times p 多算了 kxk - x 次)。所以最后的答案应该减掉 x×p×(kx)x \times p \times (k - x),那么最后的答案应该是:

    $$ans = \max_{i=0}^k (pre_{row_i} + pre_{col_{k-i}} - i \times p \times (i - p)) $$

    tips:inf-\inf 要开到 1e18-1e18

    参考代码

    #define matrix(_x, _y, _z) vector<vector<int>>(_x, vector<int>(_y, _z))
    #define debug(_x) cout << #_x << '=' << _x << endl
    using i64 = long long;
    using i128 = __int128;
    using pii = pair<int, int>;
    using mat = vector<vector<int>>;
    using u64 = unsigned long long;
    constexpr int N = 2e5 + 10;
    // dont use umap!!!
    
    signed main()
    {
        IOS;
        int n,m,k,p;
        cin >> n >> m >> k >> p;
        auto g = matrix(n + 1, m + 1, 0);
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                cin >> g[i][j];
        priority_queue<int> heaprow, heapcol;
        for(int i = 1; i <= n; i ++) // row
        {
            int sum = 0;
            for(int j = 1; j <= m; j ++)
            {
                sum += g[i][j];
            }
            heaprow.push(sum);
        }
        for(int i = 1; i <= m; i ++) // col
        {
            int sum = 0;
            for(int j = 1; j <= n; j ++)
            {
                sum += g[j][i];
            }
            heapcol.push(sum);
        }
        i64 ans = -1e18;
        vector<int> precol(k + 1), prerow(k + 1);
        for(int i = 1; i <= k; i ++)
        {
            auto colsum = heapcol.top();
            auto rowsum = heaprow.top();
            heapcol.pop();
            heaprow.pop();
            precol[i] = precol[i - 1] + colsum;
            prerow[i] = prerow[i - 1] + rowsum;
            heapcol.push(colsum - n * p);
            heaprow.push(rowsum - m * p);
        }
        for(int i = 0; i <= k; i ++)
        {
            ans = max(ans, prerow[i] + precol[k - i] - i * (k - i) * p);
        }
        cout << ans << '\n';
        return 0;
    }
    
    • 1

    信息

    ID
    230
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    14
    已通过
    2
    上传者