当前位置:首页 > 题解目录 > 正文内容

植树节

亿万年的星光7个月前 (10-05)题解目录661

【题目描述】

植树节快要到了,学校要组织志愿者去给树苗浇水。有一排树苗,编号依次是 0,1,2, . . . 。现有 n个志愿者去给树苗浇水,第 i 个志愿者选定了一个区间[ai, bi],表示第 i个志愿者将 [ai,bi] 这一区间内的每一棵树都浇一次水。如某个志愿者选择的浇水区间为 [4,9] ,表示他将给编号为 4,5,6,7,8,9 的树各浇水一次。当所有的志愿者完成各自所选区间的浇水后,可能有些树苗被不同的志愿者浇水多次,也可能有的树苗一次也没被浇过水。请你求出浇水最多的树苗被浇了多少次

【输入描述】

第 1 行,一个整数 n,表示志愿者的人数。
第 2 行到第 n + 1 行,每行两个整数 ai, bi( i= 0,1,2, . . . n− 1) ,表示志愿者 i 选择的浇水区间

【输出描述】

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

【样例输入1】

4
0 2
2 4
1 4
6 7

【样例输出1】

3

【样例输入2】

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

【样例输出2】

4

对于所有的数据:n≤ 105;0 ≤ ai≤ bi ≤ 106 。

测试点编号ai<=bi<=n<=特殊性质
1,2,3103103103
4,5,6,7106106105
8106106105ai=bi
9106106105ai=1,bi=103
10106106105

【参考答案】

#include <bits/stdc++.h>
using namespace std;
int diff[1000002],waterCount[1000001]; //差分数组与浇水数组 
int main() {
    int n;
    cin >> n;
    // 使用差分数组来记录区间加法操作
    for (int i = 0; i < n; ++i) {
        int ai, bi;
        cin >> ai >> bi;
        // 在差分数组中记录区间加法操作
        diff[ai]++;
        diff[bi + 1]--;
    }
    // 计算每棵树的实际浇水次数
    int currentWater = 0;
    int maxWaterCount=-1;
    for (int i = 0; i <= 1000000; ++i) {
        currentWater += diff[i];
        waterCount[i] = currentWater;
        maxWaterCount=max(maxWaterCount,waterCount[i]); // 找出浇水次数最多的树苗
    }
    cout << maxWaterCount <<endl;
    return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】小X与机器人

【题解】小X与机器人

【题目描述】小X的老师很喜欢围棋。众所周知,围棋的棋盘有19行19列,共有361个交叉点。为方便起见,我们把这些行列按顺序编号为1~19,并用(x, y)表示第x列第y行的位置。例如下图中,A用(16...

【题解】吃糖果

【题解】吃糖果

【题目描述】小明终于从小红手里赢走了所有的糖果,小明转变吃掉所有糖果,但是小明吃糖果有个特殊癖好,就是不喜欢将一样的糖果放在一起吃,喜欢先吃一种,下一次吃另外一种。试问小明是否存在一种吃糖果的顺序使得...

【题解】给定和为定数

【题目描述】给出若干个整数,询问其中是否有一对数的和等于给定的数。【输入描述】第一行是整数n(0 < n ≤ 100,000),表示有n个整数。第二行是n个整数。整数的范围是在0到108之间。第...

质数环

【题目描述】有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻两个数(包括首尾)的和都为素数,称为素数环。为了简便起见,我们规定每个素数环都从1开始。例如,下面就是6的一个素数环。1 4 3...

【题解】幸运儿

【题目描述】n 个人围成一圈, 并依次编号1~n,从编号为1 的人开始,按顺时针方向每隔一人选出一个,当一圈结束之后,剩下的人重新围成一圈,再次从编号1的人开始,如此循环直到剩下两人,这剩下的两人就是...

八皇后2

【题目描述】会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 × 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。对于某个满足要求的8...