Codeforces Canda Cup 2016

A、B:模拟

C、构造下就行了

D、题意:n个参加ACM的队(n<=300000),每个队都有自己的初始气球数和重量,规定如果气球数>重量,那么此队就会飞起来,淘汰出局,你现在是第一组,你可以给其他组气球,问你最高能排名多少,你的排名是气球数严格大于你气球数的队伍数+1。

   分析:贪心的想法,将那些气球数大于你的队伍放在优先队列里维护wi-ti的最小值,优先淘汰wi-ti小的队伍,给他气球的同时,你也会气球减少,也就可能有其他你后面的队伍比你高,这些队要新加入优先队列。

      具体的操作是将所有队伍按照气球多少从小到大排序,从后往前扫,扫到当前气球数<你的气球数为止,将后面的这些加入优先队列。取出最小的淘汰他,再将指针往前移动,看看是否能有新的进入优先队列,直至扫完并且优先队列出队完毕。在这个过程中,优先队列的长度一直都在变化,其中长度的最小值+1就是你的最好排名了。

原文地址:https://www.cnblogs.com/wmrv587/p/5991554.html