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;
}