当前位置：首页 > article >正文

Acwing.1343 挤牛奶(区间合并or差分)

article 2025/2/1 18:47:26

题解

每天早上 5点，三名农夫去牛场给奶牛们挤奶。

现在从 5点开始按秒计时，第一名农夫在第 300秒开始给牛挤奶，并在第 1000秒停止挤奶。

第二名农夫在第 700秒开始给牛挤奶，并在第 1200秒停止挤奶。

第三名农夫在第 1500秒开始给牛挤奶，并在第 2100秒停止挤奶。

从开始挤奶到挤奶完全结束，这一期间，至少存在一名农夫正在挤奶的连续时间段的长度最长900秒（第 300秒至第 1200秒），完全没有任何农夫在挤奶的连续时间段的长度最长为 300秒（第 1200秒至第 1500秒）。

现在给你 N名农夫挤 N头奶牛的工作时间表，请你求出：

至少存在一名农夫正在挤奶的连续时间段的最长长度。没有任何农夫在挤奶的连续时间段的最长长度。
注意：本题中给出的所有时间均为时刻（时间点），因此在本题中挤奶区间 [100，200]和 [201,300]中间会有长度为 1秒的间歇时间。

输入格式

第一行包含整数 N，表示农夫数量。

接下来 N行，每行包含两个非负整数 l,r，表示农夫挤奶的开始时刻和结束时刻。

输出格式

共一行，包含两个整数，分别表示最长连续挤奶时间以及最长连续无人挤奶时间。

数据范围

1≤N≤5000,0≤l≤r≤106

输入样例：

输出样例：

900 300

题解（博主用拆分比较多，就选用了拆分方法，区间合并的代码附上y总代码）

拆分

import java.util.Scanner;

/**
 * @author akuya
 * @create 2024-03-16-11:12
 */
public class Main {
    static int N=5010;
    static int M=1000010;
    static int n;
    static int b[]=new int[M];

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int tn=n;
        int max=0;
        int min=Integer.MAX_VALUE;
        while(tn--!=0){
            int l,r;
            l=scanner.nextInt();
            r=scanner.nextInt();
            max=Math.max(max,Math.max(l,r));
            min=Math.min(min,Math.min(l,r));
            b[l]++;
            b[r]--;
        }
        for(int i=min;i<=max+1;i++){
            if(i!=0){
                b[i]+=b[i-1];
            }
            
        }
        int ta=0,tb=0;
        int maxa=0,maxb=0;
        for(int i=min;i<=max+1;i++){
            if(b[i]>=1){
                ta++;
                maxb=Math.max(tb,maxb);
                tb=0;

            }else{
                tb++;
                maxa=Math.max(ta,maxa);
                ta=0;

            }
        }

        System.out.println(maxa+" "+maxb);
    }
}

区间合并

#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
PII segs[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &segs[i].x, &segs[i].y);
    sort(segs, segs + n);

    int res1 = 0, res2 = 0;
    int l = segs[0].x, r = segs[0].y;

    for (int i = 1; i < n; i ++ )
        if (segs[i].x <= r) r = max(r, segs[i].y);
        else
        {
            res1 = max(res1, r - l);
            res2 = max(res2, segs[i].x - r);
            l = segs[i].x, r = segs[i].y;
        }

    res1 = max(res1, r - l);
    printf("%d %d\n", res1, res2);

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/8028756/
来源：AcWing

思路

这道题是一道区间合并的的标准模板题，只需要在区间和并的代码基础上添加几行代码即可。同时也可以使用差分来做同样很简单很好理解，所以这道题不过多讲解，不懂区间合并和差分的可以看看博主的其他两个博客，给出下面两个链接。
https://blog.csdn.net/qq_62235017/article/details/130588622
https://blog.csdn.net/qq_62235017/article/details/131380110

查看全文

http://www.kler.cn/a/271414.html