游客 注册 | 登录
中文 | En

2300 - 1-2-1 Milking Cows 挤牛奶

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶，一直到1000秒。第二个农民在700秒开始，在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位):

  • 最长至少有一人在挤奶的时间段。
  • 最长的无人挤奶的时间段。（从有人挤奶开始算起）

题目输入

一个整数N。

每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。

题目输出

一行，两个整数，即题目所要求的两个答案。

输入/输出样例

输入格式

3
300 1000
700 1200
1500 2100

输出格式

900 300

C++解答

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Line{
  int startPoint;
  int endPoint;
};
bool Cmpare(Line &lineA,Line &lineB){
  return lineA.startPoint <lineB.startPoint;
}

int main(void){
  int n = 0;
  // printf("请输入农民数量N:");
  scanf("%d",&n);
  Line line[n];
  for(int i = 0;i<n;i++){
    // printf("%d\n",i);
    int startTime ,endTime = 0;
    scanf("%d%d",&line[i].startPoint,&line[i].endPoint);
  }
  // printf("************\n");
  sort(line,line+n,Cmpare);
  // for(int i = 0;i<n;i++){
  //   printf("%d %d\n",line[i].startPoint,line[i].endPoint);
  // }
  Line lineMerge[n];
  lineMerge[0].startPoint = line[0].startPoint;
  lineMerge[0].endPoint = line[0].endPoint;
  int lineNum = 1;
  for(int i = 1;i<n;i++){
    if(line[i].startPoint <= lineMerge[lineNum-1].endPoint){
    //如果下一段的起始点在上一段终点前，说明有可能可以合并，作判断
      if(line[i].endPoint >= lineMerge[lineNum-1].endPoint){
        lineMerge[lineNum-1].endPoint = line[i].endPoint;
      }
    }else{
      // 如果下一段的起始点超过上一段终点，则计算新的线段
      lineMerge[lineNum].startPoint = line[i].startPoint;
      lineMerge[lineNum].endPoint = line[i].endPoint;
      lineNum = lineNum +1;
    }
  }
  // for(int i = 0;i<lineNum;i++){
  //   printf("%d %d\n",lineMerge[i].startPoint,lineMerge[i].endPoint);
  // }
  int maxTime = lineMerge[0].endPoint - lineMerge[0].startPoint;
  int minTime = 0;
  for(int i = 1;i<lineNum;i++){
    if(lineMerge[i].endPoint - lineMerge[i].startPoint>maxTime){
      maxTime = lineMerge[i].endPoint - lineMerge[i].startPoint;
    }
    if(lineMerge[i].startPoint - lineMerge[i-1].endPoint>minTime){
      minTime = lineMerge[i].startPoint - lineMerge[i-1].endPoint;
    }
  }
  printf("%d %d",maxTime,minTime);
}
请先登陆