1 条题解

  • 0
    @ 2025-5-7 11:15:30

    要解决这个问题,我们需要计算将积木从初始状态调整到目标状态所需的最少移动次数。每次操作只能移动一个积木。

    解题思路

    关键观察
    对于每个房间,若初始积木数多于目标数,则多余的部分必须被移出。由于每次移动一个积木,总移动次数等于所有房间需要移出的积木数之和。这是因为每个移出操作对应一次移动到其他房间的移入操作,无需额外计算。

    步骤

    1. 遍历每个房间:比较初始状态和目标状态的积木数。
    2. 累加差值:若某房间初始积木数超过目标值,计算差值并累加到总移动次数中。
    3. 输出结果:累加的总差值即为最少移动次数。

    数学推导
    设第 ii 个房间的初始积木数为 fif_i,目标积木数为 gig_i。最少移动次数为:

    i=0K1max(figi,0)\sum_{i=0}^{K-1} \max(f_i - g_i, 0)

    示例分析

    • 输入:初始各房间积木数为 [1, 1, 1],目标为 [2, 0, 1]
    • 计算:第一个房间无需移出,第二个房间移出 11 个,第三个房间无需移出。总移动次数为 11

    该方法时间复杂度为 O(K)O(K),空间复杂度 O(K)O(K),高效可靠。

    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    
    #define maxn 20
    
    int n, m, k;
    int f[maxn], g[maxn];
    
    void input()
    {
    	scanf("%d%d%d", &n, &m, &k);
    	for (int i = 0; i < k; i++)
    		scanf("%d", &f[i]);
    	for (int i = 0; i < k; i++)
    		scanf("%d", &g[i]);
    }
    
    void work()
    {
    	int ans = 0;
    	for (int i = 0; i < k; i++)
    		if (f[i] > g[i])
    			ans += f[i] - g[i];
    	printf("%d\n", ans);
    }
    
    int main()
    {
    	//freopen("t.txt", "r", stdin);
    	input();
    	work();
    	return 0;
    }
    • 1

    信息

    ID
    1860
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者