📝 算法日记 | 初识 STL vector，用三道经典题开启“动态数组”之旅！🚀

🌟 今日心情

终于啃下了 C++ STL 里的重头戏——vector（向量）！🎉
以前用数组总担心越界，还要手动管理大小，现在有了 vector，感觉像拥有了一个能自动伸缩的“魔法口袋”！🪄
虽然作为初学者，我的代码可能还带着点“笨拙”和“暴力”，但这正是我成长的脚印呀～ 👣
今天整理了三道 NOIP 普及组的经典题目，记录一下我的解题思路（和踩坑过程）。大佬们轻喷，欢迎在评论区教我优化！🙏

---

🌳 第一站：P1047 [校门外的树]

📖 题目一句话：马路上一排树，给定几个要移走的区间，求剩多少棵？

💡 萌新思路：

1. 把每个移走区间存进 vector<pair<int,int>>。
2. 先排序，让区间按起点从小到大排好队。
3. 遍历合并重叠的区间（比如 [1, 5] 和 [3, 8] 合并成 [1, 8]）。
4. 算出总共移走了多少棵树，用总数减去它！

⚠️ 注意点：区间是闭区间，计算数量时要 +1 哦！

#include<bits/stdc++.h>
using namespace std;

int main() {
    vector<pair<int, int>> intervals;
    int l, m;
    cin >> l >> m;
    for (int i = 0; i < m; ++i) {
        int start, end;
        cin >> start >> end;
        intervals.push_back({start, end});
    }
    sort(intervals.begin(), intervals.end());

    int sum = 0;
    int current_start = intervals[0].first;
    int current_end = intervals[0].second;

    for (int i = 1; i < m; ++i) {
        if (intervals[i].first <= current_end) {
            current_end = max(intervals[i].second, current_end);
        } else {
            sum += (current_end - current_start + 1);
            current_start = intervals[i].first;
            current_end = intervals[i].second;
        }
    }
    sum += (current_end - current_start + 1);
    cout << l + 1 - sum;
    return 0;
}

---

🎲 第二站：P1059 [明明的随机数]

📖 题目一句话：生成一堆随机数，要去重 + 排序输出。

💡 萌新思路：
这题简直是 vector + sort 的送分题！🎁

1. 把所有数扔进 v1。
2. sort 一下，瞬间有序。
3. 再搞个 v2，遍历 v1，如果当前数和前一个不一样，就放进 v2（完美去重！）。

✨ 小得意：虽然用了两个 vector 有点占内存，但逻辑超级清晰，小白也能看懂！😎

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, num;
    cin >> n;
    vector<int> v1;
    for (int i = 0; i < n; ++i) {
        cin >> num;
        v1.push_back(num);
    }

    sort(v1.begin(), v1.end());

    vector<int> v2;
    for (int i = 0; i < v1.size(); ++i) {
        if (i > 0 && v1[i] == v1[i - 1]) {
            continue;
        }
        v2.push_back(v1[i]);
    }

    cout << v2.size() << endl;
    for (int i : v2) {
        cout << i << " ";
    }
    return 0;
}

---

🐟 第三站：P1428 [小鱼比可爱]

📖 题目一句话：每只鱼只能看左边，统计有多少只鱼比自己“不可爱”（数值更小）。

💡 萌新思路：
这道题我用了最直观的双重循环（暴力美学？🤔）。

1. 外层循环控制第 i 只鱼。
2. 内层循环从 0 扫到 i-1，数一数比 v[i] 小的有几个。
3. 结果存进 v2 输出。

🤔 自我反思：
我知道对于大数据量 $O(n^2)$ 会超时，但题目说 $n\le 100$，所以… 嘿嘿，能 AC 就是好代码！以后学了树状数组再来优化它！💪

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, num;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; ++i) {
        cin >> num;
        v.push_back(num);
    }

    vector<int> v2;
    v2.push_back(0); // 第一条鱼前面没有鱼，肯定是0

    for (int i = 1; i < n; ++i) {
        int count = 0;
        for (int j = 0; j < i; ++j) {
            if (v[j] < v[i]) {
                count++;
            }
        }
        v2.push_back(count);
    }

    for (int i : v2) {
        cout << i << " ";
    }
    return 0;
}

---

📝 今日复盘 & 碎碎念

✅ 收获：

• 彻底搞懂了 push_back() 和 size()。
• 学会了用 vector 配合 sort 解决去重问题。
• 明白了区间合并的基本逻辑。

❌ 不足：

• 变量命名太随意了（v1, v2 这种名字被大神看到估计要皱眉😅）。
• 第三题算法效率不高，属于“大力出奇迹”。
• 还没学会用迭代器，全是用的下标访问。

🌈 写在最后：
编程就像升级打怪，现在的“笨办法”是为了将来写出“神操作”打基础！
如果你也是刚开始学 C++，或者有什么更好的解法，一定要在评论区告诉我呀！ 👇 我们一起交流，一起变强！

---

本文代码均为作者原创，未经修改，真实记录初学者心路历程。
欢迎关注【算法日记】，见证一个小白的进阶之路！ ✨