luogu4188 [USACO18JAN]Lifeguards S

http://www.elijahqi.win/2018/02/02/luogu4188-usaco18janlifeguards-s/
题意翻译

FJ为他的奶牛们建造了一个游泳池，FJ认为这将有助于他们放松身心以及生产更多牛奶。

为了确保奶牛们的安全，FJ雇佣了N头牛，作为泳池的救生员，每一个救生员在一天内都会有一定的事情，并且这些事情都会覆盖一天内的一段时间。为了简单起见，泳池从时间t=0时开门，直到时间t=1000000000关门，所以每个事情都可以用两个整数来描述，给出奶牛救生员开始以及结束事情的时间。例如，一个救生员在时间t=4时开始事情并且在时间t=7时结束事情，那么这件事情就覆盖了3个单位时间。（注意：结束时间是“点”的时间）

不幸的是，FJ雇佣了多于一名的救生员，但他没有足够的资金来雇佣这些救生员。因此他必须解雇一名救生员，求可以覆盖剩余救生员的轮班时间的最大总量是多少？如果当时至少有一名救生员的事情已经开始，则这个时段被覆盖。

输入格式

输入的第一行包括一个整数N（1≤N≤100000）。接下来N行中，每行告诉了我们一个救生员在0~10000000000范围内的开始以及结束时间。所有的结束时间都是不同的。不同的救生员的事情覆盖的时间可能会重叠。

输出格式

如果FJ解雇一名救生员仍能覆盖的最大时间。

感谢@Shan_Xian 提供的翻译
题目描述

Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.

To ensure safety, he hires

NN

N cows as lifeguards, each of which has a shift that covers some contiguous interval of time during the day. For simplicity, the pool is open from time

t=0t=0

t=0 until time

t=1,000,000,000t = 1,000,000,000

t=1,000,000,000 on a daily basis, so each shift can be described by two integers, giving the time at which a cow starts and ends her shift. For example, a lifeguard starting at time

t=4t = 4

t=4 and ending at time

t=7t = 7

t=7 covers three units of time (note that the endpoints are “points” in time).

Unfortunately, Farmer John hired 1 more lifeguard than he has the funds to support. Given that he must fire exactly one lifeguard, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.
输入输出格式

输入格式：

The first line of input contains

NN

N (

1≤N≤100,0001 leq N leq 100,000

1≤N≤100,000 ). Each of the next

NN

N lines describes a lifeguard in terms of two integers in the range

0…1,000,000,0000 ldots 1,000,000,000

0…1,000,000,000 , giving the starting and ending point of a lifeguard’s shift. All such endpoints are distinct. Shifts of different lifeguards might overlap.

输出格式：

Please write a single number, giving the maximum amount of time that can still be covered if Farmer John fires 1 lifeguard.
输入输出样例

输入样例#1： 复制

3
5 9
1 4
3 7

输出样例#1： 复制

7

给定n条线段 然后询问删除哪条使得覆盖的剩余长度最长 一开始想了个错误的方法 首先先把区间转点 然后跑线段树 每次看哪条线段被覆盖大于等于2的段数多就 选择删掉哪条 但这显然是错的

所以其实应该和扫描线一样看线段覆盖 然后每次枚举删除哪个 线段树更新一下答案比较大小

注意扫描线的时候被覆盖的标记是不可以被下放的 而是应该统计下被覆盖的次数 如果被覆盖的次数边成0了那么我被覆盖的长度就应该是由下面更新上来

#include<cstdio>
#include<algorithm>
#define N 220000
#define inf 0x3f3f3f3f
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();}
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
    return x*f;
}
struct node{
    int l,r,left,right,len,cov;
}tree[N<<1],a[N];
int n,st[N],ed[N],root,num,tot,q[N],st1[N],ed1[N],ans=0;;
inline void update(int x){
    if (tree[x].cov) return;
    int l=tree[x].left,r=tree[x].right;
    tree[x].len=tree[l].len+tree[r].len;
}
inline void build(int &x,int l,int r){
    x=++num;if (l==r) {tree[x]=a[l];return;}int mid=l+r>>1;
    build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);
    tree[x].l=tree[tree[x].left].l;tree[x].r=tree[tree[x].right].r;
}
inline void modify(int x,int l,int r,int l1,int r1,int v){
    if (l1<=l&&r1>=r) {tree[x].cov+=v;
        if (tree[x].cov==1) tree[x].len=tree[x].r-tree[x].l;
        if (!tree[x].cov) update(x);return;}
    int mid=l+r>>1;
    if (l1<=mid) modify(tree[x].left,l,mid,l1,r1,v);
    if (r1>mid) modify(tree[x].right,mid+1,r,l1,r1,v);update(x);
}
inline void print(int x){
    if (tree[x].left) print(tree[x].left);
    printf("%d %d %dn",tree[x].l,tree[x].r,tree[x].len);
    if (tree[x].right) print(tree[x].right);
}
int main(){
    freopen("lifeguards.in","r",stdin);
    freopen("lifeguards.out","w",stdout);
    n=read();
    for (int i=1;i<=n;++i) st[i]=read(),ed[i]=read(),q[++tot]=st[i],q[++tot]=ed[i];sort(q+1,q+tot+1);
    int nn=unique(q+1,q+tot+1)-q-1;for (int i=1;i<nn;++i) a[i].l=q[i],a[i].r=q[i+1];build(root,1,nn-1);
    for (int i=1;i<=n;++i) st1[i]=lower_bound(q+1,q+nn+1,st[i])-q,ed1[i]=lower_bound(q+1,q+nn+1,ed[i])-q-1;
    --nn;for (int i=1;i<=n;++i) modify(root,1,nn,st1[i],ed1[i],1);//print(root),puts("dfs");    //printf("%dn",tree[root].len);

    for (int i=1;i<=n;++i){
        modify(root,1,nn,st1[i],ed1[i],-1);ans=max(ans,tree[root].len);modify(root,1,nn,st1[i],ed1[i],1);
    }
    printf("%dn",ans);
    return 0;
}

最后

以上就是糊涂金毛为你收集整理的luogu4188 [USACO18JAN]Lifeguards S的全部内容，希望文章能够帮你解决luogu4188 [USACO18JAN]Lifeguards S所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。