首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

USACO Milking Cows:區間合併統計擠奶與空閒最長時間

     編輯:關於C++

題目大意

N 個農夫擠奶,各自有一個時間區間 [start, end]。求:
1. 至少有一人擠奶的最長連續時間。
2. 無人擠奶的最長連續時間(在最早開始與最晚結束之間)。

算法流程

  1. 讀入所有區間,按 start 升序、end 升序排序。
  2. 維護當前合併區間 [curL, curR],初始為第一個區間。
  3. 遍歷剩餘區間:
     若 start ≤ curR:合併,curR = max(curR, end),更新最長擠奶時間。
     否則:出現空閒,更新最長空閒時間 start - curR,開啟新合併區間 [start, end]。
  4. 輸出兩個最大值。

C++ 實現

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved