解题思路

  1. 题目分析：

    • 种卡片，每包干脆面随机包含一张
    • 每种卡片出现概率相等
    • 对第 种卡片需要收集至少 张
    • 求满足至少一个愿望的最少购买包数

  2. 解题策略：

    • 对于每种卡片，要收集 张
    • 由于每次只能得到一张卡片，至少需要 次额外尝试
    • 再加上第一次必须的尝试，总共需要 次

代码

#include <iostream>
using namespace std;

int main() {
    long n;
    cin >> n;
    
    // 计算总共需要的次数
    long ans = 0;
    for(int i = 0; i < n; i++) {
        long p;
        cin >> p;
        ans += (p - 1);  // 每种卡片需要额外(p-1)次尝试
    }
    
    cout << ans + 1 << endl;  // 加上第一次必需的尝试
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        
        // 计算总共需要的次数
        long ans = 0;
        for(int i = 0; i < n; i++) {
            long p = sc.nextLong();
            ans += (p - 1);  // 每种卡片需要额外(p-1)次尝试
        }
        
        System.out.println(ans + 1);  // 加上第一次必需的尝试
    }
}

n = int(input())
cards = [int(input()) for _ in range(n)]

# 计算总共需要的次数
ans = sum(p - 1 for p in cards)  # 每种卡片需要额外(p-1)次尝试
print(ans + 1)  # 加上第一次必需的尝试

算法及复杂度

  • 算法：数学计算
  • 时间复杂度： - 只需要遍历一次输入数组
  • 空间复杂度： - 只需要常数级别的额外空间