首页 > 试题广场 >

植树节

[编程题]植树节

热度指数：44 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 植树节即将来临，学校决定组织志愿者为一排编号从 $0$ 开始、向右无限延伸的树苗浇水。
$\hspace{15pt}$ 共有 $n$ 名志愿者，第 $i$ 名志愿者选择了闭区间 $[a_i,b_i]$ ，并为区间内的每一棵树苗各浇一次水。
$\hspace{15pt}$ 所有志愿者完成任务后，某些树苗可能被多名志愿者重复浇水，而另一些树苗一次也没有被浇水。
$\hspace{15pt}$ 请你计算被浇水次数最多的树苗最终被浇了多少次。

输入描述:

在一行上输入一个整数 ，表示志愿者数量。 
此后  行，第  行输入两个整数 ，表示第  名志愿者浇水的树苗编号区间。

输出描述:

输出一行一个整数，表示被浇水次数最多的树苗被浇水的次数。

示例1

输入

输出

说明

在该样例中： 
区间  覆盖树苗 ； 
区间  覆盖树苗 ； 
区间  覆盖树苗 ； 
区间  覆盖树苗 。 
最终树苗  被浇水  次，为最大值，故输出 。

示例2

输入

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

输出

说明

在该样例中，编号为  的树苗被四名志愿者同时浇水，故答案为 。

算法知识视频讲解

C++

牛客207135092号

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

const int N=1e6+5;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,l,r;
    cin>>n;
    int max_num=-1;
    vector<int> cf(N,0);
    while(n--){
        cin>>l>>r;
        cf[l]++;
        cf[r+1 ]--;
        max_num=max(r,max_num);
    }
    int a=cf[0];
    int ans=a;
    for(int i=1;i<=max_num;i++){
        a=a+cf[i];
        ans=max(ans,a);
    }
    cout<<ans;
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2025-07-06 16:56:50 回复(0)