题解 | #小苯的粉丝关注#

题目链接

小苯的粉丝关注

题目描述

小苯有 $n$ 个旧账号，第 $i$ 个账号有 $a_i$ 个粉丝。他想让一个新账号的粉丝数恰好达到 $x$ 。

他可以通过以下两种方式涨粉：

单次推荐：在一个旧账号 $i$ 上发文推荐，新账号涨粉 $\lfloor a_i / 2 \rfloor$ 。每个账号都可以进行一次单次推荐。
多次推荐：选择最多一个旧账号 $j$ 进行多次推荐，新账号涨粉 $a_j$ 。

如果一个账号被选择了“多次推荐”，则不能再用它进行“单次推荐”。要求使用最少数量的旧账号，达成目标粉丝数 $x$ 。如果无法做到，输出 -1。

思路分析

这是一个组合优化问题，要求使用最少的物品（账号）凑出特定的背包容量（粉丝数 $x$ ）。由于数据范围 $n, x \le 100$ ，这是一个典型的动态规划（背包问题）场景。

问题的核心在于“最多一个账号可以被多次推荐”这个特殊约束。我们可以通过在 DP 状态中增加一个维度来处理这个约束。

1. DP 状态定义

我们定义一个二维 DP 数组 dp[j][k]：

dp[j][0]：表示新账号粉丝数恰好为 $j$ 时，在不使用“多次推荐”的情况下，所需要的最少旧账号数量。
dp[j][1]：表示新账号粉丝数恰好为 $j$ 时，在使用且仅使用一次“多次推荐”的情况下，所需要的最少旧账号数量。

我们的目标是求 min(dp[x][0], dp[x][1])。

2. DP 初始化

我们将 dp 数组的所有值初始化为一个极大值（代表无穷大），表示初始状态不可达。唯一的例外是 dp[0][0] = 0，表示粉丝数为 0 时，不需要任何账号，且没有使用“多次推荐”。

3. DP 状态转移

我们遍历每一个旧账号 $i$ （粉丝数为 $a_i$ ），然后更新整个 dp 数组。对于每个账号，我们有两种贡献方式：

单次推荐：贡献 $c_i = \lfloor a_i / 2 \rfloor$ 的粉丝。
多次推荐：贡献 $a_i$ 的粉丝。

对于每个账号 $i$ 和每个可能的粉丝数 $j$ (从 $x$ 到 $0$ )，我们考虑如何更新 dp[j][0] 和 dp[j][1]：

更新 dp[j][0] (不使用多次推荐)
- 要达到粉丝数 $j$ 且不使用多次推荐，我们只能让当前账号 $i$ 进行单次推荐。
- 这要求我们在处理账号 $i$ 之前，已经能够用其他账号通过单次推荐达到 $j - c_i$ 的粉丝数。
- 转移方程：dp[j][0] = min(dp[j][0], dp[j - c_i][0] + 1)
更新 dp[j][1] (使用一次多次推荐)
- 这种情况有两种可能来源： a. 当前账号 $i$ 作为单次推荐使用。这意味着“多次推荐”的名额已经被之前某个账号用掉了。 - 转移方程：dp[j][1] = min(dp[j][1], dp[j - c_i][1] + 1) b. 当前账号 $i$ 作为多次推荐使用。这意味着在处理账号 $i$ 之前，所有账号都必须是单次推荐。 - 转移方程：dp[j][1] = min(dp[j][1], dp[j - a_i][0] + 1)

为了确保每个账号只被使用一次（0/1背包特性），内层循环中对粉丝数 $j$ 的遍历需要从 $x$ 向下递减到 0。

4. 最终结果

遍历完所有账号后，dp[x][0] 和 dp[x][1] 就存储了最终的答案。我们取两者中的较小值。如果该值仍为无穷大，则表示无法凑出 $x$ ，输出 -1。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // dp[j][0]: min items for sum j, no multiple promo
    // dp[j][1]: min items for sum j, one multiple promo
    vector<vector<int>> dp(x + 1, vector<int>(2, INF));
    dp[0][0] = 0;

    for (int val : a) {
        int c_val = val / 2;
        int a_val = val;
        for (int j = x; j >= 0; --j) {
            // Update state 1 (one multiple promo used)
            // Case 1a: current val is normal promo, multiple promo was used before
            if (j >= c_val && dp[j - c_val][1] != INF) {
                dp[j][1] = min(dp[j][1], dp[j - c_val][1] + 1);
            }
            // Case 1b: current val is the multiple promo
            if (j >= a_val && dp[j - a_val][0] != INF) {
                dp[j][1] = min(dp[j][1], dp[j - a_val][0] + 1);
            }
            
            // Update state 0 (no multiple promo used)
            if (j >= c_val && dp[j - c_val][0] != INF) {
                dp[j][0] = min(dp[j][0], dp[j - c_val][0] + 1);
            }
        }
    }

    int result = min(dp[x][0], dp[x][1]);

    if (result >= INF) {
        cout << -1 << endl;
    } else {
        cout << result << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        final int INF = 1_000_000_000;
        int[][] dp = new int[x + 1][2];
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }
        dp[0][0] = 0;

        for (int val : a) {
            int c_val = val / 2;
            int a_val = val;
            for (int j = x; j >= 0; j--) {
                // Update state 1 (one multiple promo used)
                // Case 1a: current val is normal promo, multiple promo was used before
                if (j >= c_val && dp[j - c_val][1] != INF) {
                    dp[j][1] = Math.min(dp[j][1], dp[j - c_val][1] + 1);
                }
                // Case 1b: current val is the multiple promo
                if (j >= a_val && dp[j - a_val][0] != INF) {
                    dp[j][1] = Math.min(dp[j][1], dp[j - a_val][0] + 1);
                }
                
                // Update state 0 (no multiple promo used)
                if (j >= c_val && dp[j - c_val][0] != INF) {
                    dp[j][0] = Math.min(dp[j][0], dp[j - c_val][0] + 1);
                }
            }
        }

        int result = Math.min(dp[x][0], dp[x][1]);

        if (result >= INF) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }
}

n, x = map(int, input().split())
a = list(map(int, input().split()))

# dp[j][0]: min items for sum j, no multiple promo
# dp[j][1]: min items for sum j, one multiple promo
inf = float('inf')
dp = [[inf] * 2 for _ in range(x + 1)]
dp[0][0] = 0

for val in a:
    c_val = val // 2
    a_val = val
    for j in range(x, -1, -1):
        # Update state 1 (one multiple promo used)
        # Case 1a: current val is normal promo, multiple promo was used before
        if j >= c_val and dp[j - c_val][1] != inf:
            dp[j][1] = min(dp[j][1], dp[j - c_val][1] + 1)
        # Case 1b: current val is the multiple promo
        if j >= a_val and dp[j - a_val][0] != inf:
            dp[j][1] = min(dp[j][1], dp[j - a_val][0] + 1)
            
        # Update state 0 (no multiple promo used)
        if j >= c_val and dp[j - c_val][0] != inf:
            dp[j][0] = min(dp[j][0], dp[j - c_val][0] + 1)

result = min(dp[x][0], dp[x][1])

if result == inf:
    print(-1)
else:
    print(result)

算法及复杂度

算法：动态规划 (0/1 背包变种)
时间复杂度： $O(n \cdot x)$ 。
- 我们需要遍历 $n$ 个账号，对于每个账号，都需要遍历 $x$ 个粉丝数状态来更新 DP 表。因此，总时间复杂度为 $O(n \cdot x)$ 。
空间复杂度： $O(x)$ 。
- DP 数组的大小为 $(x+1) \times 2$ ，所以空间复杂度为 $O(x)$ 。