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容器实现，后期可以用效率更高的手写堆排序实现），每次将其中产奶量的最小值和其他整体进行比较，当奶牛被卖后重新维护该整体，即可大大减少计算量。