#UVa:10191-Longest Nap

照著題目找出空檔取最大值即可得解。

P.S.

  1. 注意還有[10:00~測資總開始時間]以及[測資總結束時間~18:00]這兩段空檔。
  2. 輸入的資料並不會以開始時間來作排序,排序得自己排。

C++(0.008)

/*******************************************************/
/* UVa 10191 Longest Nap                               */
/* Author: LanyiKnight [at] knightzone.studio             */
/* Version: 2012/03/29                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int,int> Time;

struct Schedule_item{
  Time start;
  Time end;
};

bool cmp( Schedule_item a, Schedule_item b ){
  if( a.start.first < b.start.first ) return true;
  else if( a.start.first == b.start.first && a.start.second < b.start.second ) return true;
  return false;
}

int main(){
  Time time1, time2, now, nap;
  int minutes, num, day = 1, sc_index;
  string s;
  Schedule_item *sc;

  while( scanf( "%d", &num ) != EOF ){
    now.first = 10;
    now.second = 0;
    minutes = 0;
    sc_index = 0;
    sc = new Schedule_item [num+5];

    for( int i = 0 ; i < num ; i++ ){
      scanf( "%d:%d %d:%d", &time1.first, &time1.second, &time2.first, &time2.second );
      getline( cin, s );
      sc[sc_index].start = time1;
      sc[sc_index++].end = time2;
    }

    sort( sc, sc+num, cmp );

    for( int i = 0 ; i < num ; i++ ){
      if( sc[i].start.first > now.first || (sc[i].start.first == now.first && sc[i].start.second > now.second ) ){
        if( (sc[i].start.first - now.first) * 60 + (sc[i].start.second - now.second) > minutes ){
          minutes = (sc[i].start.first - now.first) * 60 + (sc[i].start.second - now.second);
          nap.first = now.first;
          nap.second = now.second;
        }
      }

      now.first = sc[i].end.first;
      now.second = sc[i].end.second;
    }

    if( (18 - now.first) * 60 + (0 - now.second) > minutes ){
      minutes = (18 - now.first) * 60 + (0 - now.second);
      nap.first = now.first;
      nap.second = now.second;
    }


    printf( "Day #%d: the longest nap starts at %02d:%02d and will last for ", day++, nap.first, nap.second );
    if( minutes >= 60 )
      printf( "%d hours and ", minutes/60 );
    printf( "%d minutes.\n", minutes%60 );
  }

  return 0;
}
廣告

Comment

There is no comment on this post. Be the first one.

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: