A. Olympiad Date 详细题解

一、问题重述

给定一个数字序列 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 9$），按顺序依次取数字。判断最早在第几个数字取完后，可以拼出日期 01.03.2025（忽略小数点，即需要数字：0,1,0,3,2,0,2,5）。

注意：前导零必须保留，所以 0 必须出现两次（日期 01 和月份 03 中的第一个 0，以及年份 2025 中的 0 也需要）。实际所需数字统计如下：

数字	出现次数
$0$	3 次
$1$	1 次
$2$	2 次
$3$	1 次
$5$
其他	0 次

输出最小步数；如果无法凑齐，输出 $0$。

---

二、核心思路

2.1 需求统计

日期 01.03.2025 去掉小数点后的数字序列为：

$$0,1,0,3,2,0,2,5$$

统计每个数字出现次数：

$$\text{cnt}_0 = 3,\quad \text{cnt}_1 = 1,\quad \text{cnt}_2 = 2,\quad \text{cnt}_3 = 1,\quad \text{cnt}_5 = 1 $$

2.2 贪心计数

从左到右遍历输入数字，维护每个数字已出现的次数。当满足：

$$\text{cnt}[0] \ge 3,\ \text{cnt}[1] \ge 1,\ \text{cnt}[2] \ge 2,\ \text{cnt}[3] \ge 1,\ \text{cnt}[5] \ge 1 $$

时，输出当前索引（从 $1$ 开始）作为答案。如果遍历完仍未满足，输出 $0$。

2.3 正确性证明

• 因为必须按顺序取数字，不能跳过，所以最早满足条件的位置就是最小步数。
• 条件只关心数字出现次数，不关心顺序（因为日期中数字顺序固定，但只需要凑齐个数，任何顺序都可以组成 01.03.2025，因为可以重新排列）。
• 贪心是有效的：一旦计数满足，后续数字不需要再取。

---

三、时间复杂度

每个测试用例 $O(n)$，其中 $n \le 20$，$t \le 10^4$，总复杂度 $O(t \cdot n) \le 2 \times 10^5$，完美通过。

---

四、标程代码

#include <iostream>
using namespace std;

void solve() {
    int n;
    cin >> n;
    int cnt[10] = {0};  // 计数数组，初始化为 0
    bool found = false;
    
    for (int i = 0; i < n; i++) {
        int dig;
        cin >> dig;
        cnt[dig]++;
        
        // 检查是否满足所有条件
        if (cnt[0] >= 3 && cnt[1] >= 1 && cnt[2] >= 2 &&
            cnt[3] >= 1 && cnt[5] >= 1 && !found) {
            cout << i + 1 << endl;  // 输出步数（1-indexed）
            found = true;
        }
    }
    
    if (!found) cout << 0 << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

五、示例验证

示例 1

10
2 0 1 2 3 2 5 0 0 1

• 前 8 个数字：2,0,1,2,3,2,5,0
cnt[0]=2, cnt[1]=1, cnt[2]=3, cnt[3]=1, cnt[5]=1，缺一个 0
• 第 9 个数字 0：cnt[0]=3，满足所有条件 → 输出 9 ✅

示例 2

8
2 0 1 2 3 2 5 0

• 遍历完：cnt[0]=2 不足 3 → 输出 0 ✅

示例 3

8
2 0 1 0 3 2 5 0

• 前 7 个数字：2,0,1,0,3,2,5
cnt[0]=2, cnt[1]=1, cnt[2]=2, cnt[3]=1, cnt[5]=1，缺一个 0
• 第 8 个数字 0：cnt[0]=3，满足 → 输出 8 ✅

示例 4

16
2 3 1 2 3 0 1 9 2 1 0 3 5 4 0 3

• 前 14 个数字后：cnt[0]=2 缺一个 0
• 第 15 个数字 0：满足 → 输出 15 ✅

---

六、总结

数字	所需次数
$0$	3
$1$	1
$2$	2
$3$	1
$5$

本题是一个简单的贪心计数问题，核心是统计每个数字出现次数，一旦达到目标就输出当前步数。由于 $n$ 很小，也可以直接暴力模拟，但标程的写法更简洁高效。