USACO 1.2_挤牛奶_离散

发布于 2019-04-30  916 次阅读


题目描述

的任务是编一个程序,读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表,计算以下两点(均以秒为单位):
• 最长至少有一人在挤奶的时间段。
• 最长的无人挤奶的时间段。


思路

排序后每一次维护一个区间begin 和 end
当枚举到的数和区间有变化时就更改区间值,并更改ans


/*
ID: a1192631
PROG: milk2
LANG: C++
*/
#include 
#include 
#define max(x,y) x>y?x:y
using namespace std;
struct arr
{
    int x,y;
};
arr a[30001];
int cam(arr a,arr b)
{
    return a.xend)
                end=a[i].y;
        }
        else 
        {
            ans1=max(end-begin,ans1);
            ans=max(a[i].x-end,ans);
            begin=a[i].x;
            end=a[i].y;
        }
    }
    printf("%d %d\n",ans1,ans);
}
]]>