Lesson 0001 · vector：你的第一个竞赛利器

① 程序设计基础 — 第 1 课

1. 为什么是 vector？

在算法竞赛里，几乎每一道题都要存一堆数据 —— 分数、坐标、数列、矩阵。用 C 的原生数组 int a[1000]，你得提前猜大小，还容易越界。C++ 的 vector 就是来解决这个问题的。

2. 基本操作

记住这四个操作，就够开始做题了：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;           // 声明一个空的 vector

    v.push_back(42);         // 往末尾加一个元素
    v.push_back(7);
    v.push_back(100);

    cout << v.size() << endl;    // 输出：3
    cout << v[0] << endl;        // 输出：42 （下标访问）

    // 用范围 for 遍历
    for (int x : v) {
        cout << x << ' ';       // 输出：42 7 100
    }
    return 0;
}

3. 竞赛输入模版

蓝桥杯和 ACM 的题目通常格式是：先给你 n，再给你 n 个数。学会下面这个模式，它就是你的肌肉记忆：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;                    // 先读个数
    vector<int> a(n);             // 直接开 n 个位置
    for (int i = 0; i < n; i++) {
        cin >> a[i];             // 逐个读入
    }

    // 现在 a 里就有所有数据了，想怎么处理就怎么处理
    return 0;
}

还有一种写法，如果你不确定会有多少个数（读到读完为止）：

vector<int> a;
int x;
while (cin >> x) {              // 读到 EOF 为止
    a.push_back(x);
}

4. 热身题：求 n 个数的和

输入：第一行一个整数 n，第二行 n 个整数。
输出：这 n 个数的和。

#include <iostream>
#include <vector>
using namespace std;

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

    int sum = 0;
    for (int x : a) sum += x;    // 范围 for 求和
    cout << sum << endl;
    return 0;
}

5. 坑点清单

• 下标从 0 开始：3 个元素的 v，合法下标只有 0、1、2，v[3] 已经是越界。
• 越界不报错：v[i] 读越界不会崩，只会拿到脏数据。调试时换成 v.at(i)，它会当场报错，帮你把问题炸出来。
• size() 和 capacity() 不是一回事：size() 是「实际装了几个」，capacity() 是「内部预留了多大」，数个数永远用 size()。
• vector<int> a(n) 不是空表：它已经开了 n 个位置（值为 0）。想从空表开始，就写 vector<int> a;。
• 循环读入停不下来：while (cin >> x) 只在读到 EOF 时结束，本地要按 Ctrl+Z 再回车，否则会一直等输入。
• 头文件别漏：vector 要 #include <vector>，输入输出要 #include <iostream>。

6. 小测

7. 动手练习

打开 洛谷 P1046 · 陶陶摘苹果，用刚学的 vector 解决它。

思路：读入 10 个苹果高度 → 存进 vector<int> → 读入陶陶伸手高度 → 遍历判断哪些苹果的高度不大于伸手高度加 30。

卡住时的自查顺序

1. 样例答案对不对？先把 10 个高度和伸手高度都打印出来，确认读进来的数没问题。
2. 循环的边界写对了吗？10 个苹果是 i = 0 到 i < 10，别写成 i <= 10。
3. 条件方向对不对？题目要的是「够得着」，即高度 ≤ 伸手高度 + 30。
4. 输出行不行？OJ 通常只认一个整数，别多打提示文字。

本课小结

• vector 是默认容器：大小自动增长，不用提前猜。
• 四个基本操作：push_back 加、size() 数个数、v[i] 取、范围 for 遍历。
• 输入套路：先读 n，再 vector<int> a(n)，然后逐个 cin >> a[i]。
• 下标从 0 开始，越界不报错，调试时用 at() 把错误逼出来。
• size() 才是个数，capacity() 只是内部预留的空间。