https://www.luogu.org/problemnew/show/P1204

C++版本一 

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q,ans;
struct node{
    int l,r;
    bool operator <(const node&S)const{
        if(l==S.l)
            return r<S.r;
        return l<S.l;
    }

}e[N];
int a[N],b[N],c[N];
char str;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    int x=1;
    int y=1;
    int max1=0;
    int max2=0;
    int cnt1=0;
    int cnt2=0;
    for(int i=a[1];i<=b[n];i++){
        while(a[x]==i&&x<=n)x++,t++;
        while(b[y]==i&&y<=n)y++,t--;
        c[i]=t;
        if(c[i]==0){
            cnt2++;
            max1=max(max1,cnt1);
            cnt1=0;
        }else{
            cnt1++;
            max2=max(max2,cnt2);
            cnt2=0;
        }


    }
    //max1=max(max1,cnt1);
    //max2=max(max2,cnt2);
    cout << max1 <<" "<< max2 << endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解:

差分的思想:用O(1)的复杂度来表示一次O(n)的覆盖:设b[i]=a[i]-a[i-1],则当a[l]到a[r]均增加一时,则只需b[l]++,b[r+1]--,其余的由于前后两相差未变,b不需改动。这样,便可以用b来表示a的变化。(最后将b复原成a即可)。另一点需要注意的:题意有些坑人:一个挤牛奶时间段(a,b)说的是从第a秒一直到b-1秒,所以这里不是b[r+1]--,而是b[r]--。、

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int c[1000002]={0};//差分数列
int main()
{
    int start=2e9,end=-2e9;//最大最小值初始值,用于计算开始和结束挤牛奶的时间
    int n;//读入数据个数
    int a,b;//挤牛奶时段
    int tf=1;
    int t[2]={0};//tf=1:计算最长有人挤牛奶时段,用t[1]记录;tf=0:计算最长无人挤牛奶时段,用t[0]记录
    int nstart;//用于计算t[0]和t[1]
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        c[a]++;
        c[b]--;//差分
        start=min(start,a);
        end=max(end,b-1);//取最大值和最小值
    }
    nstart=start;//区间开始时间点
    int nc;
    end++;//保证计算的正确性,及最后的挤牛奶时段总时长能计算正确
    for(int i=start;i<=end;i++)
    {
        c[i]=c[i-1]+c[i];//恢复a数组
        nc=c[i]==0?0:1;//c[i]是否大于0
        if(nc!=tf||i==end)//是否可以统计
        {
            t[tf]=max(t[tf],i-nstart);//取最长时段,计算时段
            nstart=i;//取新的时间开始点
            tf=1-tf;//换一类进行计算
        }
    }
    printf("%d %d",t[1],t[0]);//输出,记得t[0],t[1]顺序
    return 0;
}