题目链接

蛇鸟

题目描述

蛇鸟是一种类似于蛇和鸟的可爱生物。蛇鸟的主要食物是水果，每吃一个水果，它的长度就会增加 1。

水果离地面具有一定的高度，第 个果实的高度为 。蛇鸟可以吃到小于等于其当前长度的水果。

当蛇鸟的初始长度为 时，求它吃水果能达到的最大长度。

输入:

  • 第一行给出水果的数量 和蛇鸟初始长度 。
  • 第二行给出 个整数，代表每个水果的高度。

输出:

  • 一个整数，表示蛇鸟能达到的最大长度。

解题思路

这是一个典型的贪心算法问题。

为了让蛇鸟能够吃到尽可能多的水果，从而使长度最大化，它应该采取最优的策略。最优策略是总是选择当前能够吃到的、高度最低的水果。

为什么这是最优的呢？因为吃任何一个能吃到的水果，长度都会增加 1。选择吃更高的水果并不会带来额外的好处，反而可能因为初始长度不够，错失了吃掉低处水果、增加长度去够更高水果的机会。因此，先吃最容易吃到的（即高度最低的），可以保证我们以最快的速度增加长度，去解锁更多之前够不到的水果。

所以，算法步骤如下：

  1. 读取所有水果的高度。
  2. 将所有水果的高度从小到大进行排序。
  3. 遍历排序后的水果高度数组，对于每一个水果：
    • 如果蛇鸟的当前长度大于或等于该水果的高度，那么蛇鸟就吃掉它，并且长度加 1。
    • 如果蛇鸟的当前长度小于该水果的高度，那么它无法吃掉这个水果。由于水果已经按高度排序，它也无法吃掉后面的任何水果。此时可以提前结束遍历。
  4. 遍历结束后，蛇鸟的长度就是能达到的最大长度。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    long long l;
    // 读取水果数量 n 和初始长度 l
    cin >> n >> l;
    vector<int> h(n);
    // 读取每个水果的高度
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    
    // 将水果按高度升序排序
    sort(h.begin(), h.end());
    
    // 遍历排序后的水果
    for (int i = 0; i < n; ++i) {
        if (l >= h[i]) {
            // 如果能吃到，长度加 1
            l++;
        } else {
            // 如果吃不到，由于已经排序，后续也一定吃不到，提前退出
            break;
        }
    }
    
    // 输出最终长度
    cout << l << endl;
}

int main() {
    solve();
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取水果数量 n
        int n = sc.nextInt();
        // 读取初始长度 l
        long l = sc.nextLong();
        int[] h = new int[n];
        // 读取每个水果的高度
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }
        
        // 将水果按高度升序排序
        Arrays.sort(h);
        
        // 遍历排序后的水果
        for (int i = 0; i < n; i++) {
            if (l >= h[i]) {
                // 如果能吃到，长度加 1
                l++;
            } else {
                // 如果吃不到，由于已经排序，后续也一定吃不到，提前退出
                break;
            }
        }
        
        // 输出最终长度
        System.out.println(l);
    }
}

def solve():
    # 读取水果数量 n 和初始长度 l
    n, l = map(int, input().split())
    # 读取每个水果的高度
    h = list(map(int, input().split()))
    
    # 将水果按高度升序排序
    h.sort()
    
    # 遍历排序后的水果
    for height in h:
        if l >= height:
            # 如果能吃到，长度加 1
            l += 1
        else:
            # 如果吃不到，由于已经排序，后续也一定吃不到，提前退出
            break
            
    # 输出最终长度
    print(l)

solve()

算法及复杂度

  • 时间复杂度: ，其中 是水果的数量。主要的时间开销在于对水果高度数组的排序。
  • 空间复杂度: ，用于存储水果的高度。如果输入数据可以被修改，也可以使用原地排序，空间复杂度可以达到 （取决于排序算法的实现）。