题解 | #植树节#

植树节

https://www.nowcoder.com/practice/bf18f4e68f614b35a7a6c56c743d82fc

植树节

思路

题目在说什么?有 个志愿者,每人负责给编号 的树苗各浇一次水,问被浇水次数最多的树苗被浇了多少次。

这是经典的差分数组问题。对区间 全部加 1,等价于在差分数组上 ++ 和 --。所有操作做完后,对差分数组求前缀和就能还原每个位置的实际值,取最大值即可。

复杂度

  • 时间:,其中 是坐标上界(
  • 空间:

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    const int MAXN = 1000002;
    vector<int> diff(MAXN + 1, 0);
    for(int i = 0; i < n; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        diff[l]++;
        if(r + 1 <= MAXN) diff[r + 1]--;
    }
    int ans = 0, cur = 0;
    for(int i = 0; i <= MAXN; i++){
        cur += diff[i];
        ans = max(ans, cur);
    }
    printf("%d\n", ans);
    return 0;
}
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int MAXN = 1000002;
        int[] diff = new int[MAXN + 1];
        for (int i = 0; i < n; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            diff[l]++;
            if (r + 1 <= MAXN) diff[r + 1]--;
        }
        int ans = 0, cur = 0;
        for (int i = 0; i <= MAXN; i++) {
            cur += diff[i];
            ans = Math.max(ans, cur);
        }
        System.out.println(ans);
    }
}
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    MAXN = 1000002
    diff = [0] * (MAXN + 2)
    for _ in range(n):
        l, r = map(int, input().split())
        diff[l] += 1
        if r + 1 <= MAXN:
            diff[r + 1] -= 1
    ans = 0
    cur = 0
    for i in range(MAXN + 1):
        cur += diff[i]
        if cur > ans:
            ans = cur
    print(ans)

main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const MAXN = 1000002;
    const diff = new Int32Array(MAXN + 2);
    for (let i = 1; i <= n; i++) {
        const [l, r] = lines[i].split(' ').map(Number);
        diff[l]++;
        if (r + 1 <= MAXN) diff[r + 1]--;
    }
    let ans = 0, cur = 0;
    for (let i = 0; i <= MAXN; i++) {
        cur += diff[i];
        if (cur > ans) ans = cur;
    }
    console.log(ans);
});
全部评论

相关推荐

03-10 11:23
门头沟学院 Java
鹿LF:计算机面试就跟数学题一样,没什么实际价值,但只能这么筛选,本质是考察你的努力,智力和学习能力
点赞 评论 收藏
分享
03-26 13:04
已编辑
电子科技大学 算法工程师
xiaowl:你这个简历“条目上”都比较有深度性,但是实际上面试官又没法很好的评估你是怎么达到很多看上去很厉害的结果的。要避免一些看上去很厉害的包装,比如高效的内存复用策略的表达,如果仅是简单的一些内存共享机制,而且面试上也没有深挖的空间,就不要这样表达。比如,工程化模式本质上可能就是定义了一些abstract class,那也就没特别多值得讲的内容。建议简历上应该侧重那些你花了大量时间和精力解决、研究的问题,不要过分追求“丰富”,而是关注在技术深入度、问题解决能力的表现上。
没有实习经历,还有机会进...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务