首页 > 代码库 > 挤牛奶 milking
挤牛奶 milking
【题目描述】：
三个农民每天清晨5 点起床,然后去牛棚给3 头牛挤奶.第一个农民在300 时刻(从5 点开始计时,秒为单位)给他的牛挤奶,一直到1000 时刻.第二个农民在700 时刻开始,在 1200 时刻结束.第三个农民在1500 时刻开始2100 时刻结束.期间最长的至少有一个农民在挤奶的连续时间为900 秒(从300 时刻到1200 时刻),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300 秒(从1200 时刻到1500 时刻).你的任务是编一个程序,读入一个有N 个农民(1 <= N <= 5000)挤N 头牛的工作时间列表,计算以下两点(均以秒为单位):
• 最长至少有一人在挤奶的时间段.
• 最长的无人挤奶的时间段.
【输入描述】：
Line 1: 一个整数N.
Lines 2..N+1: 每行两个小于1000000 的非负整数,表示一个农民的开始时刻与结束时刻.
【输出描述】：
一行,两个整数,即题目所要求的两个答案.
【样例输入】 | 【样例输出】 |
3 300 1000 700 1200 1500 2100 | 900 300 |
【数据范围及描述】：
贪心水题，但要注意特殊情况
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn=5005; 8 9 int N;10 struct node11 {12 int l,r;13 bool operator<(node p)const{return l<p.l;}14 }A[maxn];15 16 17 int main()18 {19 scanf("%d",&N);20 for(int i=1;i<=N;i++)21 scanf("%d %d",&A[i].l,&A[i].r);22 sort(A+1,A+N+1);23 int s,e;24 s=A[1].l,e=A[1].r;25 int ans1=0,ans2=0;26 for(int i=2;i<=N;i++)27 {28 if(A[i].l<=e) e=max(e,A[i].r);29 else30 {31 ans1=max(ans1,e-s);32 ans2=max(A[i].l-e,ans2);33 s=A[i].l;34 e=A[i].r;35 }36 }37 ans1=max(ans1,e-s);38 printf("%d %d",ans1,ans2);39 return 0;40 }
挤牛奶 milking
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。