题目传送门
Milking Cows
题目大意
给你n个区间为覆盖，区间总长为最小左端点到最大右端点，求最长的覆盖区间，和最长的为覆盖区间
思路
本想练习线段树的，发现线段树有点麻烦，采取了差分做法 使用差分的方法操作区间
O
(
1
)
O(1)
O(1)即可，查询
O
(
n
)
O(n)
O(n) 区间增值即为
a
[
l
]
+
+
,
a
[
r
+
1
]
+
+
a[l]++,\ a[r+1]++
a[l]++, a[r+1]++，注意300~900其实是601秒，题目给的600秒，所以是在899结束的，所以应该是
a
[
l
]
+
+
,
a
[
r
]
+
+
a[l]++,\ a[r]++
a[l]++, a[r]++
AC Code
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std
;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
const int N
=1e6 +9;
int n
, a
[N
];
int x
, y
;
void solve(){
cin
>>n
;
int mx
=-INF
, mn
=INF
;
for(int i
=1; i
<=n
; i
++){
cin
>>x
>>y
;
a
[x
]++;
a
[y
]--;
if(x
<mn
) mn
=x
;
if(y
>mx
) mx
=y
;
}
int ans1
=0, ans0
=0;
int temp1
=0, temp0
=0, sum
=0;
for(int i
=mn
; i
<=mx
; i
++){
sum
+=a
[i
];
if(sum
==0){
temp0
++;
ans1
=max(ans1
, temp1
);
temp1
=0;
}
else{
temp1
++;
ans0
=max(ans0
, temp0
);
temp0
=0;
}
}
cout
<<ans1
<<" "<<ans0
<<endl
;
return ;
}
signed main(){
ios
::sync_with_stdio(0);
cin
.tie(0), cout
.tie(0);
#ifdef TDS_ACM_LOCAL
freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
solve();
return 0;
}
