BNUOJ 1020 信息战（六）――军队体检 （STL之优先队列）

分析：m个军医所用的时间等价于治疗病人最多的那个军医所花费的时间。先按人数排序，然后把前m大的排压入优先队列，每次出队的是先体检完的军医，队列里的最后一个元素就是体检人数最多的军医体检的人数，然后除以每个军医每天体检的人数即可求出答案。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; int a[1000005]; bool comp(int x, int y) { return x > y; } int main() { int t, n, m, p, i; //值小的优先出队，因为值小治病的时间短 priority_queue
      
       , greater
       
         > Q; scanf(%d,&t); while(t--) { scanf(%d%d%d,&n,&m,&p); while(!Q.empty()) Q.pop(); for(i = 0; i < n; i++) scanf(%d,&a[i]); sort(a, a+n, comp); //从大到小排序 for(i = 0; i < m; i++) Q.push(a[i]); //把m个最大的压入优先队列 for(i = m; i < n; i++) { int tmp = Q.top(); Q.pop(); tmp += a[i]; Q.push(tmp); } while(Q.size() > 1) //最后一个一定是最大的，即治疗病人最多的军医治疗的人数 Q.pop(); printf(%.3lf ,Q.top()*1.0/p); } return 0; }