P1204 [USACO1.2]挤牛奶Milking Cows(差分)

发布于 2020-10-05  0 次阅读


题目大意:

P1204 [USACO1.2]挤牛奶Milking Cows
给你n个区间为覆盖,区间总长为最小左端点到最大右端点,求最长的覆盖区间,和最长的为覆盖区间

思路:

本想练习线段树的,发现线段树有点麻烦,采取了差分做法
使用差分的方法操作区间O ( 1 ) O(1)O(1)即可,查询O ( n ) O(n)O(n)
区间增值即为a [ l ] + + ,   a [ r + 1 ] + + ,注意300~900其实是601秒,题目给的600秒,所以是在899结束的,所以应该是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;
}

平平无奇的在校大学生