题解 | #时津风的资源收集#

题目链接

时津风的资源收集

题目描述

共有四种资源：油、弹药、钢材、铝。每组数据给定目标资源量 $x_1,x_2,x_3,x_4$ 。进入界面时四种资源初始均为 $10$ ，且任何时刻均需保持在区间 $[10,300]$ 。每次操作可对单一资源进行以下之一：

将该资源 $\pm 1$
将该资源 $\pm 10$
将该资源 $\pm 100$
直接将该资源设为上限 $300$
直接将该资源设为下限 $10$

问使四种资源同时恰好达到目标所需的最少操作次数。

输入：

第一行一个整数 $t$
接下来 $t$ 行，每行四个整数 $x_1,x_2,x_3,x_4$

输出：

对每组数据输出一个整数，表示最少操作次数

解题思路

四种资源相互独立，答案等于对四个目标分别计算最少步数再求和。设从 $10$ 调到某一目标 $x$ 的最少步数为 $f(x)$ 。

不使用“跳到上限”的情况下，只利用 $\pm 100,\pm 10,\pm 1$ 调整差值 $d=x-10\,(\ge 0)$ 。最少步数即将 $d$ 表示为 $100,10,1$ 的线性组合时系数绝对值之和的最小值。可在百位与十位各做一次“就近取整”决策：
- 取 $a\in\{\lfloor d/100\rfloor,\lceil d/100\rceil\}$ ，余量 $r=|d-100a|$ ；
- 对 $r$ 再取 $b\in\{\lfloor r/10\rfloor,\lceil r/10\rceil\}$ ，余量 $s=|r-10b|$ ；
- 该策略的步数为 $|a|+|b|+s$ ，在两级取整的四种组合中取最小值即为 $\text{costDiff}(d)$ 。
使用一次“跳到上限 300”更快时：先 $1$ 步把值设为 $300$ ，再用 $\pm 100,\pm 10,\pm 1$ 将差值 $300-x$ 调整到位，步数为 $1+\text{costDiff}(300-x)$ 。

因此有 $f(x)=\min\{\,\text{costDiff}(x-10),\ 1+\text{costDiff}(300-x)\,\}$ 最后答案为 $\sum_{i=1}^4 f(x_i)$ 。

说明：上述序列可以按“先加后减”的顺序安排，始终保持数值落在 $[10,300]$ 内；边界 $x\in[10,300]$ 满足题意。

代码

c++
java
python

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

static inline int tens_cost(int r) {
    // r >= 0
    int b1 = r / 10;
    int rem = r % 10;
    int cost1 = b1 + rem;                  // floor 方案
    int cost2 = (rem == 0) ? b1 : (b1 + 1 + (10 - rem)); // ceil 方案
    return min(cost1, cost2);
}

static inline int cost_diff(int d) {
    // d >= 0, 只用 ±100, ±10, ±1
    int a0 = d / 100;
    int r0 = abs(d - 100 * a0);
    int ans = a0 + tens_cost(r0);
    int a1 = a0 + 1;
    int r1 = abs(100 * a1 - d);
    ans = min(ans, a1 + tens_cost(r1));
    return ans;
}

static inline int cost_to(int x) {
    // 从 10 到 x 的最少步数
    int d1 = x - 10;
    int d2 = 300 - x;
    return min(cost_diff(d1), 1 + cost_diff(d2));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; 
    if (!(cin >> t)) return 0;
    while (t--) {
        int x1, x2, x3, x4;
        cin >> x1 >> x2 >> x3 >> x4;
        long long ans = 0;
        ans += cost_to(x1);
        ans += cost_to(x2);
        ans += cost_to(x3);
        ans += cost_to(x4);
        cout << ans << "\n";
    }
    return 0;
}

import java.util.*;

public class Main {
    static int tensCost(int r) {
        int b1 = r / 10;
        int rem = r % 10;
        int cost1 = b1 + rem;
        int cost2 = (rem == 0) ? b1 : (b1 + 1 + (10 - rem));
        return Math.min(cost1, cost2);
    }
    static int costDiff(int d) {
        int a0 = d / 100;
        int r0 = Math.abs(d - 100 * a0);
        int ans = a0 + tensCost(r0);
        int a1 = a0 + 1;
        int r1 = Math.abs(100 * a1 - d);
        ans = Math.min(ans, a1 + tensCost(r1));
        return ans;
    }
    static int costTo(int x) {
        int d1 = x - 10;
        int d2 = 300 - x;
        return Math.min(costDiff(d1), 1 + costDiff(d2));
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int x1 = sc.nextInt();
            int x2 = sc.nextInt();
            int x3 = sc.nextInt();
            int x4 = sc.nextInt();
            long ans = 0;
            ans += costTo(x1);
            ans += costTo(x2);
            ans += costTo(x3);
            ans += costTo(x4);
            System.out.println(ans);
        }
    }
}

def tens_cost(r: int) -> int:
    b1, rem = divmod(r, 10)
    cost1 = b1 + rem
    cost2 = b1 if rem == 0 else (b1 + 1 + (10 - rem))
    return min(cost1, cost2)

def cost_diff(d: int) -> int:
    a0 = d // 100
    r0 = abs(d - 100 * a0)
    ans = a0 + tens_cost(r0)
    a1 = a0 + 1
    r1 = abs(100 * a1 - d)
    ans = min(ans, a1 + tens_cost(r1))
    return ans

def cost_to(x: int) -> int:
    return min(cost_diff(x - 10), 1 + cost_diff(300 - x))

T = int(input().strip())
for _ in range(T):
    x1, x2, x3, x4 = map(int, input().split())
    ans = cost_to(x1) + cost_to(x2) + cost_to(x3) + cost_to(x4)
    print(ans)

算法及复杂度

算法：分治到单资源，枚举百位与十位“就近取整”组合；与“先跳到 300 再回调”的方案取最小
时间复杂度： $\mathcal{O}(t)$ （每组常数时间）
空间复杂度： $\mathcal{O}(1)$