洛谷P1204 [USACO1.2]挤牛奶Milking Cows 题解

P1204 [USACO1.2]挤牛奶Milking Cows

题目链接：P1204 [USACO1.2]挤牛奶Milking Cows

题意：给定 $n$ 个区间，求这些区间覆盖后最长的区间和未被覆盖的最长区间（未被覆盖区间的范围在最左端到最右端内，否则就没有意义了）

正如简化的题意，我们可以使用类似于差分的思想，如图

我们可以保存左右端点，然后从左向右遍历（排序一下就行，如果左右端点相同左端点优先）

每次碰到端点加一下就行，和为0时更新答案即可

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(5005)
int n,pos,ans1,ans2,sum,last;
struct node
{int isleft,x;const bool operator <(const node &o)const{if(x==o.x)return isleft>o.isleft;return x<o.x;}
}a[MAXN<<1]; // 记得要乘2
signed main()
{scanf("%lld",&n);for(int i=1,l,r; i<=n; i++){scanf("%lld%lld",&l,&r);a[++pos]={1,l};a[++pos]={-1,r};}sort(a+1,a+1+pos);last=a[1].x;sum=1;for(int i=2; i<=pos; i++){sum+=a[i].isleft;if(!sum){ans1=max(ans1,a[i].x-last);ans2=max(ans2,a[i+1].x-a[i].x);last=a[i+1].x;}}printf("%lld %lld\n",ans1,ans2);return 0;
}

刷点水题养生qwq

转载请说明出处