前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >挤牛奶Milking Cows

挤牛奶Milking Cows

作者头像
glm233
发布2020-09-28 10:14:50
5340
发布2020-09-28 10:14:50
举报

P1204 [USACO1.2]挤牛奶Milking Cows

分析:初始化变量头和尾为第一个农民的开始时间和结束时间,max1,max2为最大重叠长度和最大不重叠长度每处理一个农民,相当于处理一条线段,首先先对每一条线段的初始端排序,接着从第二条开始处理,如果下一条线段起点小于当前尾部,说明可能有覆盖取max1=max(当前的尾,这条线段的末端),反之则开始计算最大不重叠长度max2=max(max2,当前线段起点-当前尾部)并更新头尾(分别赋值为当前线段的起点和终点)(讲的应该够详细了...

代码语言:javascript
复制
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
struct node
{
    int begin,end;
}p[5005];
bool cmp(node a,node b)
{
    return a.begin<b.begin;
}
int n,max1,max2,head,tail;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].begin>>p[i].end;
    }
    sort(p+1,p+1+n,cmp);
    head=p[1].begin,tail=p[1].end;
    for(int i=2;i<=n;i++)
    {
        if(p[i].begin<=tail)tail=max(tail,p[i].end);
        else
        {
            max1=max(max1,tail-head);
            max2=max(max2,p[i].begin-tail);
            head=p[i].begin,tail=p[i].end;
        }
    }
    max1=max(max1,tail-head);
    cout<<max1<<" "<<max2;
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/03/11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档