小红比身高

[题目链接](https://www.nowcoder.com/practice/4722fa5316a543b8b4e7c0d1bdf64942)

思路

小红可以自由选择站在哪阶楼梯上，她的总高度 = 自身身高 + 所选楼梯高度。要使她比尽可能多的朋友高，显然应该选择高度最大的楼梯。

具体步骤

1. 计算每个朋友的总高度：朋友 的总高度 = ，其中 是朋友身高， 是朋友所站楼梯的高度。
2. 选择最高的楼梯：小红的总高度 = 。
3. 统计严格小于小红总高度的朋友数：将所有朋友的总高度排序后，用二分查找找到第一个 小红总高度的位置，该位置的下标即为答案。

为什么选最高楼梯一定最优？

小红的总高度越大，能比过的朋友越多。楼梯的选择只影响小红自己的高度，不影响朋友的高度，因此直接取最大楼梯高度即可。

复杂度分析

• 时间复杂度：，排序朋友总高度的开销占主导。
• 空间复杂度：，存储朋友和楼梯信息。

代码

[sol-C++]

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    long long h;
    scanf("%d%d%lld", &n, &m, &h);
    vector<long long> a(n), p(n), s(m);
    for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
    for(int i = 0; i < n; i++) scanf("%lld", &p[i]);
    for(int i = 0; i < m; i++) scanf("%lld", &s[i]);

    vector<long long> tot(n);
    for(int i = 0; i < n; i++){
        tot[i] = a[i] + s[p[i]-1];
    }
    sort(tot.begin(), tot.end());

    long long maxS = *max_element(s.begin(), s.end());
    long long myH = h + maxS;

    // count friends with tot[i] < myH
    int ans = (int)(lower_bound(tot.begin(), tot.end(), myH) - tot.begin());
    printf("%d\n", ans);
    return 0;
}

[sol-Java]

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        long h = Long.parseLong(st.nextToken());

        long[] a = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());

        int[] p = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) p[i] = Integer.parseInt(st.nextToken());

        long[] s = new long[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) s[i] = Long.parseLong(st.nextToken());

        long[] tot = new long[n];
        for (int i = 0; i < n; i++) {
            tot[i] = a[i] + s[p[i] - 1];
        }
        Arrays.sort(tot);

        long maxS = s[0];
        for (long v : s) maxS = Math.max(maxS, v);
        long myH = h + maxS;

        // binary search: count tot[i] < myH
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tot[mid] < myH) lo = mid + 1;
            else hi = mid;
        }
        System.out.println(lo);
    }
}

[sol-Python3]

import sys
from bisect import bisect_left

input = sys.stdin.readline

n, m, h = map(int, input().split())
a = list(map(int, input().split()))
p = list(map(int, input().split()))
s = list(map(int, input().split()))

tot = sorted(a[i] + s[p[i] - 1] for i in range(n))

my_h = h + max(s)
print(bisect_left(tot, my_h))

[sol-JavaScript]

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, m, h] = lines[0].split(' ').map(Number);
    const a = lines[1].split(' ').map(Number);
    const p = lines[2].split(' ').map(Number);
    const s = lines[3].split(' ').map(Number);

    const tot = [];
    for (let i = 0; i < n; i++) {
        tot.push(a[i] + s[p[i] - 1]);
    }
    tot.sort((x, y) => x - y);

    const maxS = Math.max(...s);
    const myH = h + maxS;

    // binary search: count tot[i] < myH
    let lo = 0, hi = n;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (tot[mid] < myH) lo = mid + 1;
        else hi = mid;
    }
    console.log(lo);
});