题解 | #小红比身高#

题目链接

题目描述

小红和 $n$ 个朋友比身高。小红的身高是 $h$ ，第 $i$ 个朋友的身高是 $f_i$ 。有 $m$ 阶楼梯，第 $j$ 阶的高度是 $l_j$ 。第 $i$ 个朋友固定站在第 $p_i$ 阶楼梯上。小红可以自由选择站在任意一阶楼梯上。问小红最多可以比多少个朋友高？（身高严格大于才算“高”）

解题思路

这是一个最优化问题。我们需要找到一个最佳策略（小红站的楼梯），使得她能超过的朋友数量最大化。

朴素思路

最直接的方法是枚举小红的所有可能性。小红有 $m$ 个楼梯可以选择。

对于每一个选择，我们可以计算出小红的最终身高（自身身高 + 楼梯高度）。
然后，我们遍历所有 $n$ 个朋友，计算出每个朋友的最终身高（朋友身高 + 其所在楼梯高度），并与小红的身高进行比较，统计出超过的人数。
我们在所有 $m$ 种选择中，取一个最大的超过人数即可。
这种方法的时间复杂度为 $\mathcal{O}(n \cdot m)$ ，在 $n$ 和 $m$ 较大时可能会超时。

优化思路：排序 + 二分查找

我们可以对朴素思路进行优化。朋友们的身高和站位是固定的，因此他们的最终身高也是固定的。

预处理：首先，我们计算出所有 $n$ 个朋友的最终身高，并将这些身高存入一个数组 friend_final_heights。
排序：为了能够快速查询，我们将 friend_final_heights 数组进行升序排序。
枚举与查找：接下来，我们遍历小红的所有 $m$ 种楼梯选择。
- 对于小红的每一种选择，我们计算出她的一个最终身高 xiao_hong_height。
- 现在的任务就变成了：在已排序的 friend_final_heights 数组中，快速地找出有多少个元素严格小于 xiao_hong_height。
- 这个问题可以高效地通过二分查找来解决。我们可以使用二分查找找到数组中第一个大于或等于 xiao_hong_height 的元素的位置。这个位置的索引，就恰好是数组中严格小于 xiao_hong_height 的元素数量。
求解：我们对小红的 $m$ 个选择都重复上述过程，并记录下找到的最大计数值，即为最终答案。

这个优化算法的时间复杂度为 $\mathcal{O}(n \log n + m \log n)$ ，效率远高于朴素算法。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    long long h;
    cin >> n >> m >> h;

    vector<long long> f(n);
    for (int i = 0; i < n; ++i) cin >> f[i];

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

    vector<long long> l(m);
    for (int i = 0; i < m; ++i) cin >> l[i];

    vector<long long> friend_final_heights(n);
    for (int i = 0; i < n; ++i) {
        friend_final_heights[i] = f[i] + l[p[i] - 1];
    }

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

    int max_wins = 0;
    for (int i = 0; i < m; ++i) {
        long long xiao_hong_height = h + l[i];
        // lower_bound finds the first element not less than xiao_hong_height.
        // The distance from the beginning is the count of elements smaller than it.
        auto it = lower_bound(friend_final_heights.begin(), friend_final_heights.end(), xiao_hong_height);
        int current_wins = distance(friend_final_heights.begin(), it);
        if (current_wins > max_wins) {
            max_wins = current_wins;
        }
    }

    cout << max_wins << endl;

    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long h = sc.nextLong();

        long[] f = new long[n];
        for (int i = 0; i < n; i++) f[i] = sc.nextLong();

        int[] p = new int[n];
        for (int i = 0; i < n; i++) p[i] = sc.nextInt();

        long[] l = new long[m];
        for (int i = 0; i < m; i++) l[i] = sc.nextLong();

        long[] friendFinalHeights = new long[n];
        for (int i = 0; i < n; i++) {
            friendFinalHeights[i] = f[i] + l[p[i] - 1];
        }

        Arrays.sort(friendFinalHeights);

        int maxWins = 0;
        for (int i = 0; i < m; i++) {
            long xiaoHongHeight = h + l[i];
            int currentWins = binarySearch(friendFinalHeights, xiaoHongHeight);
            if (currentWins > maxWins) {
                maxWins = currentWins;
            }
        }
        System.out.println(maxWins);
    }

    // Find number of elements strictly less than target
    private static int binarySearch(long[] arr, long target) {
        int low = 0, high = arr.length - 1;
        int ans = 0; // count of elements < target
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < target) {
                ans = mid + 1;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }
}

import bisect

def solve():
    n, m, h = map(int, input().split())
    f = list(map(int, input().split()))
    p = list(map(int, input().split()))
    l = list(map(int, input().split()))

    friend_final_heights = []
    for i in range(n):
        height = f[i] + l[p[i] - 1]
        friend_final_heights.append(height)
    
    friend_final_heights.sort()
    
    max_wins = 0
    for i in range(m):
        xiao_hong_height = h + l[i]
        # bisect_left finds the insertion point for xiao_hong_height,
        # which is the count of elements < xiao_hong_height
        current_wins = bisect.bisect_left(friend_final_heights, xiao_hong_height)
        if current_wins > max_wins:
            max_wins = current_wins
            
    print(max_wins)

solve()

算法及复杂度

算法：排序 + 二分查找
时间复杂度： $\mathcal{O}(n \log n + m \log n)$ ，其中 $n$ 是朋友的数量， $m$ 是楼梯的数量。时间主要花费在对朋友最终身高数组的排序，以及后续对每个小红身高可能性的二分查找。
空间复杂度： $\mathcal{O}(n+m)$ ，用于存储朋友和楼梯的信息。