当前位置：首页 > article >正文

【C++】P1428 小鱼比可爱

article 2025/1/7 16:24:16

在这里插入图片描述

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

文章目录

💯前言
💯题目说明
- 题目输入格式
- 题目输出格式
- 样例
- - **输入样例**
  - **输出样例**
- 题目解析
💯解法分析
- 我的做法
- - 代码
  - 解法说明
  - 时间复杂度
- 老师的做法
- - 代码
  - 解法说明
  - 总结
  - 时间复杂度
💯解法优化
- 使用树状数组优化
- - 核心思路
  - 实现代码
  - 时间复杂度分析
- 优化总结
💯小结

在这里插入图片描述

💯前言

C++是一门学习成本不高，但深度极大的编程语言，特别适合用于计算机解题和合理化计算程序。在本文中，我不仅对题目 P1428 小鱼比可爱进行详细分析，还将给出全面优化和提升思路，并提供一些解题的扩展思考。此文标题全展，起首展示题目和算法，中段分析并比较不同解法，最后给出一些高效解法应用和态度深选。希望通过本文，让读者不仅能思考优化思路，还能展开观念，学习极致算法应用。
C++ 参考手册

💯题目说明

P1428 小鱼比可爱
在这里插入图片描述

在此题目中，小鱼参加一场“比可爱”比赛。比赛的规则如下：每只小鱼的可爱度以一个整数表示，在自己的视野里，计算自己左边有几只鱼的可爱度比自己低。

题目输入格式

第一行：一个正整数 n，表示小鱼的数量（最多为 100 只）。
第二行：一个长度为 n 的正整数列表，为小鱼的可爱度，用空格分隔。

题目输出格式

一行：一个长度为 n 的正整数列表，用空格分隔，表示每只小鱼左边比它可爱度低的鱼的数量。

样例

输入样例

6
4 3 0 5 1 2

输出样例

0 0 0 3 1 2

题目解析

题目要求每只小鱼，计算左边有几只鱼的可爱度比它低。

样例解析如下：

第 1 只小鱼：没有左边的鱼，因此输出 0。
第 2 只小鱼：左边为 [4] ，没有可爱度比 3 小的，因此输出 0。
第 3 只小鱼：左边为 [4, 3] ，没有可爱度比 0 小的，因此输出 0。
第 4 只小鱼：左边为 [4, 3, 0] ，有 3 只鱼可爱度比 5 小，因此输出 3。
第 5 只小鱼：左边为 [4, 3, 0, 5] ，有 1 只鱼可爱度比 1 小，因此输出 1。
第 6 只小鱼：左边为 [4, 3, 0, 5, 1] ，有 2 只鱼可爱度比 2 小，因此输出 2。

上述每个步骤通过一次简单遍历即可解决，但解决总时间复杂度为 $n^2$ 。

💯解法分析

我的做法

代码

#include <iostream>
using namespace std;

const int N = 100;
int arr[N];

int main()
{
    int n = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }

    for(int i = 1; i <= n; i++)
    {
        int count = 0;
        for(int j = i - 1; j >= 1; j--)
        {
            if(arr[j] < arr[i])
                count++;
        }
        cout << count << " ";
    }

    return 0;
}

在这里插入图片描述

解法说明

输入：
- 通过 cin 输入小鱼数量和可爱度。
- 将可爱度保存在数组 arr 中，使用 1-based 下标（从 1 开始）。
结构解析：
- 外层循环从第 1 只小鱼起，按顺序遍历所有小鱼。
- 内层循环倒序测量所有左侧鱼，如果比当前小鱼可爱度小，则计数。
输出：
- 每个小鱼结果通过 cout 输出，用空格分隔。

时间复杂度

外层循环：运行 n 次。
内层循环：对每只小鱼，从左到右最多运行 i-1 次。
总时间复杂度： $n^2$ 。

该代码简单直接，能有效解决题目要求，但时间复杂度较高，当小鱼数量较大时效率会较低。

老师的做法

代码

#include <iostream>
using namespace std;

const int N = 110;
int arr[N];

int main()
{
    int n = 0;
    cin >> n;
    // 输入数据
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    // 统计
    for (int i = 0; i < n; i++)
    {
        int count = 0;
        for (int j = 0; j < i; j++)
        {
            if (arr[j] < arr[i])
            {
                count++;
            }
        }
        cout << count << " ";
    }

    return 0;
}

在这里插入图片描述

解法说明

输入部分：
- 使用 0-based 数组（从 0 开始），方便与 C++ 数组操作习惯保持一致。
- 用一个 for 循环输入小鱼可爱度。
统计部分：
- 外层循环遍历每只小鱼，内层循环遍历当前小鱼左侧的所有小鱼。
- 内层通过条件判断 arr[j] < arr[i]，统计左侧比当前小鱼可爱度低的数量。
输出部分：
- 每次外层循环完成后，输出当前小鱼的统计结果。

总结

老师的代码与之前代码的逻辑基本一致，但采用了 0-based 数组下标，符合 C++ 常规习惯，代码风格稍微简洁一些。

时间复杂度

同样是 $n^2$ ，适合小规模问题解答。

💯解法优化

使用树状数组优化

为了优化时间复杂度，可以使用**树状数组（Fenwick Tree）**统计比当前小鱼可爱度低的数量，将时间复杂度降为 $n l o g (ma x A)$ ，其中 maxA 为可爱度的最大值。

核心思路

构建树状数组：
- 树状数组用于动态维护每种可爱度的频率。
- 初始状态下，所有频率为 0。
遍历小鱼并更新：
- 对于每只小鱼，查询树状数组中比当前小鱼可爱度低的数量，即为结果。
- 然后更新当前小鱼的可爱度频率。

实现代码

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

const int MAX_A = 11; // 最大可爱度是10

int fenwick[MAX_A] = {0};

// 更新树状数组
void update(int index, int value) {
    while (index < MAX_A) {
        fenwick[index] += value;
        index += index & -index;
    }
}

// 查询前缀和
int query(int index) {
    int sum = 0;
    while (index > 0) {
        sum += fenwick[index];
        index -= index & -index;
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = 0; i < n; i++) {
        // 查询当前小鱼左边比它小的数量
        cout << query(arr[i]) << " ";
        // 更新当前小鱼的可爱度
        update(arr[i] + 1, 1);
    }

    return 0;
}