题解：P12988 [GCJ 2022 #1B] Controlled Inflation

lailai0916 · 2025-07-03 11:44:07 · 题解

题意简述

你需要控制充气泵的气压，依次为 n 位顾客的产品充气，每位顾客有 p 个产品，目标是最小化按钮按压次数。

泵的初始气压为 0，每次可调整 \pm 1，每位顾客内部的产品顺序可自由选择，但顾客的整体顺序不能改变。

解题思路

顾客优化

设第 i 位顾客的产品最大气压为 a_i，最小气压为 b_i。

显然，无论以什么顺序处理，气压一定需要覆盖 a_i 和 b_i 这两个极值，其余产品的气压都会被经过。

因此，只需要考虑最大和最小两个极值。

状态设计

对于每位顾客的极值气压，有两种方案：a_i\to b_i 和 b_i\to a_i。

这两种方案的内部代价都是 a_i-b_i，区别仅在于进入和离开时的位置。

设前 i 位顾客处理完后，停在 b_i 的最小代价为 f_{i,0}，停在 a_i 的最小代价为 f_{i,1}。

状态转移

若停留在 b_i，先从上一位顾客的终态到达 a_i，再内部降到 b_i：

若停留在 a_i，先到 b_i，再升到 a_i：

特别地，对于第一位顾客，可以令：

最终答案为最后一位顾客的两种方案的最小值，即：

滚动数组

由于状态仅与上一位顾客相关，可使用滚动数组优化，将空间复杂度降至 O(1)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
ll f[2][2];
int mx[2],mn[2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    for(int $=1;$<=T;$++)
    {
        int n,p;
        cin>>n>>p;
        f[0][0]=f[0][1]=mx[0]=mn[0]=0;
        for(int i=1;i<=n;i++)
        {
            mx[i&1]=0;mn[i&1]=inf;
            for(int j=1;j<=p;j++)
            {
                int x;
                cin>>x;
                mx[i&1]=max(mx[i&1],x);
                mn[i&1]=min(mn[i&1],x);
            }
            f[i&1][0]=mx[i&1]-mn[i&1]+min
            (
                f[i&1^1][0]+abs(mn[i&1^1]-mx[i&1]),
                f[i&1^1][1]+abs(mx[i&1^1]-mx[i&1])
            );
            f[i&1][1]=mx[i&1]-mn[i&1]+min
            (
                f[i&1^1][0]+abs(mn[i&1^1]-mn[i&1]),
                f[i&1^1][1]+abs(mx[i&1^1]-mn[i&1])
            );
        }
        cout<<"Case #"<<$<<": "<<min(f[n&1][0],f[n&1][1])<<'\n';
    }
    return 0;
}