小鱼比可爱 - C++/Java/Python 实现及常见陷阱解析

好的，这是一个非常典型的**入门级算法题**，主要考察**数组遍历**和**计数**的基本逻辑。下面我将为你详细拆解这道题，并提供多种语言的实现方案。 --- ## 🧐 题目理解 **核心场景：** - 有 `n` 条鱼，从左到右排成一排。 - 每只鱼只能看到**它左边**的鱼（因为它头朝左）。 - 对于每只鱼，我们需要统计它左边有多少只鱼的“可爱程度”**小于**它自己。 **输入示例：** ``` 6 4 3 0 5 1 2 ``` **输出示例：** ``` 0 0 0 3 1 2 ``` **解释：** - 第1条鱼（可爱值4）：左边没有鱼 → 0 - 第2条鱼（可爱值3）：左边有4，4>3 → 0 - 第3条鱼（可爱值0）：左边有4,3，都大于0 → 0 - 第4条鱼（可爱值5）：左边有4,3,0，都小于5 → 3 - 第5条鱼（可爱值1）：左边有4,3,0,5，只有0小于1 → 1 - 第6条鱼（可爱值2）：左边有4,3,0,5,1，只有0,1小于2 → 2 --- ## 💻 算法思路（暴力法） **思路：** - 遍历所有鱼（外层循环）。 - 对于每一条鱼，再遍历它左边的所有鱼（内层循环）。 - 如果左边的鱼可爱值小于当前鱼，则计数器加1。 - 将计数器存入结果数组。 **复杂度分析：** - 时间复杂度：`O(n²)`，因为有两层循环。 - 空间复杂度：`O(n)`，用于存储结果数组。 - 由于 `n <= 100`，这种方法完全可行。 --- ## 🚀 代码实现（多语言） ### 🔹 Python 实现（推荐初学者） ```python def main(): n = int(input().strip()) cute_values = list(map(int, input().strip().split())) result = [] for i in range(n): count = 0 for j in range(i): if cute_values[j] < cute_values[i]: count += 1 result.append(str(count)) print(' '.join(result)) if __name__ == "__main__": main() ``` ### 🔹 C++ 实现（适合竞赛） ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> cute(n); for (int i = 0; i < n; ++i) { cin >> cute[i]; } vector<int> result; for (int i = 0; i < n; ++i) { int count = 0; for (int j = 0; j < i; ++j) { if (cute[j] < cute[i]) { count++; } } result.push_back(count); } for (int i = 0; i < n; ++i) { if (i > 0) cout << ' '; cout << result[i]; } cout << endl; return 0; } ``` ### 🔹 Java 实现 ```java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] cute = new int[n]; for (int i = 0; i < n; i++) { cute[i] = sc.nextInt(); } StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { int count = 0; for (int j = 0; j < i; j++) { if (cute[j] < cute[i]) { count++; } } sb.append(count).append(' '); } System.out.println(sb.toString().trim()); sc.close(); } } ``` --- ## ⚠️ 常见陷阱与优化建议 ### 常见陷阱 1. **比较方向错误**：注意是“不如自己可爱”，即**小于**当前值，不是小于等于。 2. **索引越界**：内层循环范围应为 `0` 到 `i-1`。 3. **输出格式**：题目要求每个整数之间用空格分隔，尤其是最后不能有多余空格（有些OJ对格式敏感）。 4. **输入读取**：注意处理可能存在的多余换行或空格。 ### 进阶优化思路 虽然本题 `n <= 100`，不需要优化，但如果你遇到 `n` 很大的情况（如 `n <= 10^5`），可以用**树状数组（Fenwick Tree）** 或**线段树**将时间复杂度降为 `O(n log n)`。 **大致思路：** - 由于可爱程度是整数，我们可以离散化后，从左到右遍历。 - 每遇到一个数，查询当前小于该数的数字个数，然后把这个数插入树状数组。 - 这样每次查询和更新都是 `O(log n)`。 --- ## 📚 开发建议与学习资源 ### 开发建议 1. **Code Style**：保持代码清晰、变量命名有语义，如 `cute_values` 比 `a` 更易读。 2. **调试技巧**：可以在循环中加 `print` 或 `cout` 输出中间状态，便于调试。 3. **边界测试**：一定要测试 `n=1` 的情况，以及所有鱼可爱值相同的情况。 ### 推荐学习资源 - **刷题平台**：洛谷、Codeforces、LeetCode（搜索“数组遍历”类题目） - **算法书**：《算法竞赛入门经典》（刘汝佳）、《数据结构与算法分析》 - **在线教程**：菜鸟教程、W3Schools（基础语法） --- ## 📦 这道题的关键在于： - 理解“只能看到左边”这一条件。 - 熟练运用**双重循环**进行统计。 - 注意输出格式和边界情况。 掌握这道题后，你可以尝试类似的题目，比如：“有多少个数比它小（包括右边）”、“逆序对统计”等。 --- ######[AI写代码神器 | 1421点数解答 | 2026-07-22 11:45:00]