1.1.9　奶牛的命運

【上機練習】奶牛的命運（poorcow）UVA 10273 

農夫有N頭奶牛，可由于產奶太少，他決定以后把每天產奶最少的奶牛賣給肉鋪老板，但如果當天不止一頭奶牛產奶最少，便“放過”它們。設奶牛產奶是周期性的，問最后有多少頭奶牛幸存。

【輸入格式】

第1行為一個整數T（1≤T≤500），表示有T組測試數據。

每組數據的第1行為一個整數N（N≤1000），表示奶牛總數。

隨后N行表示每頭奶牛的產奶周期（不超過10天）以及每天的產奶量（產奶量不超過250）。

【輸出格式】

輸出幸存的奶牛數（可能全被賣）及最后一頭奶牛是在哪一天被賣的。 

【輸入樣例】

1

4

4 7 1 2 9 

1 2 

2 7 1

1 2

【輸出樣例】

2 6 （2指最后剩下2頭奶牛，6指最后一頭奶牛是在第6天被賣的。）

【算法分析】

普通的模擬算法效率很低，可以試著優化。

由于每頭奶牛的產奶周期不會超過10天，因此幾頭奶牛具有同樣的產奶周期的概率很大。而具有同樣產奶周期的奶牛的“命運”是有緊密關聯的，即任意一天有奶牛被賣，假設被賣的是這幾頭奶牛中的一頭，那么它肯定是其中產奶量最少的一頭。因此，可以將具有相同“命運”的奶牛們作為一個整體來維護（前期可用STL中的multiset容器實現，后期可以用效率更高的手寫堆排序實現），每次將其中產奶量的最小值和其他整體進行比較，當奶牛被賣后重新維護該整體，即可大大減少計算量。