CF909E Coprocessor

题目大意

给定一张 DAG，其中含 n 个点和 m 条有向边。

给定两种处理器，主处理器和副处理器以及对应的点（主处理器一次只可处理一个点，副处理器一次可处理多个点）

求副处理器最少运行次数

思路

因为是 DAG ，所以想到拓扑排序。

题目要求副处理器运行次数最少，相当于要主处理器运行次数尽可能多。所以我们可以先把能处理的主处理器的任务一次性处理完，然后再处理副处理器的。

实现中，开两个队列维护两个处理器就OK了。

Code

<iframe sandbox="allow-scripts allow-same-origin" src="https://carbon.vercel.app/embed?bg=rgba%28255%2C255%2C255%2C0%29&t=one-dark&wt=none&l=text%2Fx-c%2B%2Bsrc&ds=true&dsyoff=0px&dsblur=26px&wc=true&wa=true&pv=37px&ph=38px&ln=true&fl=1&fm=Fira+Code&fs=14.5px&lh=116%25&si=false&es=4x&wm=false&code=%252F%252F%2520Problem%253A%2520CF909E%2520Coprocessor%250A%252F%252F%2520URL%253A%2520https%253A%252F%252Fwww.luogu.com.cn%252Fproblem%252FCF909E%250A%252F%252F%2520Memory%2520Limit%253A%2520250%2520MB%250A%252F%252F%2520Time%2520Limit%253A%25201500%2520ms%250A%252F%252F%2520Author%253AarlenWKX%250A%250A%2523%2520include%2520%253Cbits%252Fstdc%252B%252B.h%253E%250A%250Ausing%2520namespace%2520std%253B%250A%250Aconst%2520int%2520N%2520%253D%25201e5%2520%252B%25205%252C%2520M%2520%2520%253D%25201e5%2520%252B%25205%253B%250A%250Aint%2520n%252C%2520m%252C%2520a%2520%255B%2520N%2520%255D%253B%250Aint%2520had%2520%255B%2520N%2520%255D%252C%2520nxt%2520%255B%2520M%2520%255D%252C%2520vct%2520%255B%2520M%2520%255D%252C%2520edgenum%253B%250Aint%2520ind%2520%255B%2520N%2520%255D%253B%250Aqueue%2520%253C%2520int%2520%253E%2520q%2520%255B%25202%2520%255D%253B%250Aint%2520tot%252C%2520ans%253B%250A%250Avoid%2520adddoge%2520%28%2520int%2520u%252C%2520int%2520v%2520%29%250A%257B%250A%2509%250A%2509edgenum%2520%252B%252B%253B%250A%2509%250A%2509nxt%2520%255B%2520edgenum%2520%255D%2520%253D%2520had%2520%255B%2520u%2520%255D%253B%250A%2509vct%2520%255B%2520edgenum%2520%255D%2520%253D%2520v%253B%250A%2509had%2520%255B%2520u%2520%255D%2520%253D%2520edgenum%253B%250A%2509%250A%257D%250A%250Aint%2520main%2520%28%2520%29%250A%257B%250A%2509%250A%2509scanf%2520%28%2520%2522%2525d%2525d%2522%252C%2520%2526%2520n%252C%2520%2526%2520m%2520%29%253B%250A%2509%250A%2509for%2520%28%2520int%2520i%2520%253D%25201%253B%2520i%2520%253C%253D%2520n%253B%2520i%2520%252B%252B%2520%29%2520scanf%2520%28%2520%2522%2525d%2522%252C%2520%2526%2520a%2520%255B%2520i%2520%255D%2520%29%253B%250A%2509%2509%250A%2509for%2520%28%2520int%2520i%2520%253D%25201%252C%2520x%252C%2520y%253B%2520i%2520%253C%253D%2520m%253B%2520i%2520%252B%252B%2520%29%250A%2509%257B%250A%2509%2509scanf%2520%28%2520%2522%2525d%2525d%2522%252C%2520%2526%2520x%252C%2520%2526%2520y%2520%29%253B%250A%2509%2509adddoge%2520%28%2520%252B%252B%2520y%252C%2520%252B%252B%2520x%2520%29%253B%250A%2509%2509ind%2520%255B%2520x%2520%255D%2520%252B%252B%253B%250A%2509%2509%250A%2509%257D%250A%2509%250A%2509for%2520%28%2520int%2520i%2520%253D%25201%253B%2520i%2520%253C%253D%2520n%253B%2520i%2520%252B%252B%2520%29%250A%2509%2509if%2520%28%2520%21%2520ind%2520%255B%2520i%2520%255D%2520%29%2520q%2520%255B%2520a%2520%255B%2520i%2520%255D%2520%255D.push%2520%28%2520i%2520%29%253B%250A%2509%250A%2509while%2520%28%2520tot%2520%253C%2520n%2520%29%250A%2509%257B%250A%2509%2509%250A%2509%2509if%2520%28%2520%21%2520q%2520%255B%25200%2520%255D.empty%2520%28%2520%29%2520%29%250A%2509%2509%257B%250A%2509%2509%2509%250A%2509%2509%2509while%2520%28%2520%21%2520q%2520%255B%25200%2520%255D.empty%2520%28%2520%29%2520%29%250A%2509%2509%2509%257B%250A%2509%2509%2509%2509%250A%2509%2509%2509%2509int%2520u%2520%253D%2520q%2520%255B%25200%2520%255D.front%2520%28%2520%29%253B%2520q%2520%255B%25200%2520%255D.pop%2520%28%2520%29%253B%250A%2509%2509%2509%2509tot%2520%252B%252B%253B%250A%2509%2509%2509%2509for%2520%28%2520int%2520e%2520%253D%2520had%2520%255B%2520u%2520%255D%253B%2520e%253B%2520e%2520%253D%2520nxt%2520%255B%2520e%2520%255D%2520%29%250A%2509%2509%2509%2509%257B%250A%2509%2509%2509%2509%2509int%2520v%2520%253D%2520vct%2520%255B%2520e%2520%255D%253B%2520ind%2520%255B%2520v%2520%255D%2520--%253B%250A%2509%2509%2509%2509%2509if%2520%28%2520%21%2520ind%2520%255B%2520v%2520%255D%2520%29%2520q%2520%255B%2520a%2520%255B%2520v%2520%255D%2520%255D.push%2520%28%2520v%2520%29%253B%250A%2509%2509%2509%2509%257D%250A%2509%2509%2509%2509%250A%2509%2509%2509%257D%250A%2509%2509%2509%250A%2509%2509%257D%250A%2509%2509else%250A%2509%2509%257B%250A%2509%2509%2509%250A%2509%2509%2509ans%2520%252B%252B%253B%250A%2509%2509%2509%250A%2509%2509%2509while%2520%28%2520%21%2520q%2520%255B%25201%2520%255D.empty%2520%28%2520%29%2520%29%250A%2509%2509%2509%257B%250A%2509%2509%2509%2509int%2520u%2520%253D%2520q%2520%255B%25201%2520%255D.front%2520%28%2520%29%253B%2520q%2520%255B%25201%2520%255D.pop%2520%28%2520%29%253B%250A%2509%2509%2509%2509tot%2520%252B%252B%253B%250A%2509%2509%2509%2509for%2520%28%2520int%2520e%2520%253D%2520had%2520%255B%2520u%2520%255D%253B%2520e%253B%2520e%2520%253D%2520nxt%2520%255B%2520e%2520%255D%2520%29%250A%2509%2509%2509%2509%257B%250A%2509%2509%2509%2509%2509int%2520v%2520%253D%2520vct%2520%255B%2520e%2520%255D%253B%2520ind%2520%255B%2520v%2520%255D%2520--%253B%250A%2509%2509%2509%2509%2509if%2520%28%2520%21%2520ind%2520%255B%2520v%2520%255D%2520%29%2520q%2520%255B%2520a%2520%255B%2520v%2520%255D%2520%255D.push%2520%28%2520v%2520%29%253B%250A%2509%2509%2509%2509%257D%250A%2509%2509%2509%2509%250A%2509%2509%2509%257D%250A%2509%2509%2509%250A%2509%2509%257D%250A%2509%2509%250A%2509%257D%250A%2509%250A%2509printf%2520%28%2520%2522%2525d%2522%252C%2520ans%2520%29%253B%250A%2509%250A%2509return%25200%253B%250A%2509%250A%257D" style="width: 1000px; height: 1714px; border: 0; transform: scale(1); overflow: hidden"> </iframe>

CF725D Contest Balloons

题目大意

ACM比赛，大家都知道。AC一题会有一个气球。 现在有n(2<=n<=300000)n(2<=n<=300000) 支队伍，每支队伍的重量是 wi ，拥有 ti 个气球(wi,ti<=10^18)，当一支队伍的气球个数比它的重量都要大时，这个队伍就会飘起来，从而被取消比赛资格。 现在你带领的是1号队，你希望你队伍的名次尽可能靠前，你是个有原则的人，不会偷气球，但你可以把气球送给别的队伍，让他们飞起来。 求最终你的队伍所获得的最好名次

思路

显然，这又㕛叒叕是个贪心。为了尽可能多的迫害帮助其他队伍，我们应该优先将自己的气球分给弱势群体离飘起来所需要的气球数小且气球数量比我们多的队伍，这用排序+扫描+优先队列可以实现。

某队伍：我可谢谢您了

Code

<iframe sandbox="allow-scripts allow-same-origin" src="https://carbon.vercel.app/embed?bg=rgba%28255%2C255%2C255%2C0%29&t=one-dark&wt=none&l=text%2Fx-c%2B%2Bsrc&ds=true&dsyoff=0px&dsblur=26px&wc=true&wa=true&pv=37px&ph=38px&ln=true&fl=1&fm=Fira+Code&fs=14.5px&lh=116%25&si=false&es=4x&wm=false&code=%252F%252F%2520Problem%253A%2520CF725D%2520Contest%2520Balloons%250A%252F%252F%2520URL%253A%2520https%253A%252F%252Fwww.luogu.com.cn%252Fproblem%252FCF725D%250A%252F%252F%2520Memory%2520Limit%253A%2520250%2520MB%250A%252F%252F%2520Time%2520Limit%253A%25203000%2520ms%250A%252F%252F%2520Author%253A%2520arlenWKX%250A%250A%252F%252Foi%25E5%258D%2581%25E5%25B9%25B4%25E4%25B8%2580%25E5%259C%25BA%25E7%25A9%25BA%25EF%25BC%258C%25E4%25B8%258D%25E5%25BC%2580longlong%25E8%25A7%2581%25E7%25A5%2596%25E5%25AE%2597%250A%252F%252F%25E4%25B8%2580%25E8%2588%25AC%25E4%25B8%258D%25E5%25BB%25BA%25E8%25AE%25AE%25E7%2594%25A8%2523define%2520int%2520long%2520long%2520...%2520signed%2520main%28%29%25E8%25BF%2599%25E7%25A7%258D%25E4%25B8%259C%25E8%25A5%25BF%25EF%25BC%258C%25E9%2599%25A4%25E9%259D%259E%25E4%25BD%25A0%25E7%259C%259F%25E7%259A%2584%25E6%2590%259E%25E4%25B8%258D%25E6%25B8%2585%25E5%2593%25AA%25E4%25B8%25AA%25E8%25A6%2581%25E5%25BC%2580%25E5%2593%25AA%25E4%25B8%25AA%25E4%25B8%258D%25E8%25A6%2581%25E5%25BC%2580%250A%252F%252FSTL%25E7%259C%259F%25E9%25A6%2599%25EF%25BC%2581%25EF%25BC%2581%25EF%25BC%2581%25E6%258F%2590%25E9%25AB%2598%252B%252F%25E7%259C%2581%25E9%2580%2589--%253E%25E6%2599%25AE%25E5%258F%258A%252F%25E6%258F%2590%25E9%25AB%2598-%250A%250A%2523%2520include%2520%253Cbits%252Fstdc%252B%252B.h%253E%250A%250Ausing%2520namespace%2520std%253B%250A%250Atypedef%2520long%2520long%2520ll%253B%250A%250Aconst%2520int%2520N%2520%253D%2520300005%253B%250A%250Aint%2520n%253B%250All%2520t%252C%2520w%252C%2520a%252C%2520b%253B%250Apair%2520%253C%2520ll%252C%2520ll%2520%253E%2520doge%2520%255B%2520N%2520%255D%253B%250Apriority_queue%2520%253C%2520ll%252C%2520vector%2520%253C%2520ll%2520%253E%252C%2520greater%2520%253C%2520ll%2520%253E%2520%253E%2520pige%253B%250A%250Aint%2520main%2520%28%2520%29%250A%257B%250A%2509%250A%2509scanf%2520%28%2520%2522%2525d%2525lld%2525lld%2522%252C%2520%2526%2520n%252C%2520%2526%2520t%252C%2520%2526%2520w%2520%29%253B%250A%2509%250A%2509for%2520%28%2520int%2520i%2520%253D%25202%253B%2520i%2520%253C%253D%2520n%253B%2520i%2520%252B%252B%2520%29%250A%2509%257B%250A%2509%2509scanf%2520%28%2520%2522%2525lld%2525lld%2522%252C%2520%2526%2520a%252C%2520%2526%2520b%2520%29%253B%250A%2509%2509doge%2520%255B%2520i%2520%255D%2520%253D%2520pair%2520%253C%2520ll%252C%2520ll%2520%253E%2520%28%2520a%252C%2520b%2520%29%253B%250A%2509%257D%250A%2509%250A%2509sort%2520%28%2520doge%2520%252B%25202%252C%2520doge%2520%252B%25201%2520%252B%2520n%252C%2520greater%2520%253C%2520pair%2520%253C%2520ll%252C%2520ll%2520%253E%2520%253E%2520%28%2520%29%2520%29%253B%250A%2509%250A%2509int%2520pos%2520%253D%25202%252C%2520rank%2520%253D%25200x7fffffff%253B%250A%2509%250A%2509while%2520%28%25201%2520%29%250A%2509%257B%250A%2509%2509%250A%2509%2509for%2520%28%2520%253B%2520pos%2520%253C%253D%2520n%2520%2526%2526%2520doge%2520%255B%2520pos%2520%255D.first%2520%253E%2520t%253B%2520pos%2520%252B%252B%2520%29%250A%2509%2509%2509pige.push%2520%28%2520doge%2520%255B%2520pos%2520%255D.second%2520-%2520doge%2520%255B%2520pos%2520%255D.first%2520%252B%25201%2520%29%253B%250A%2509%2509%2509%250A%2509%2509rank%2520%253D%2520min%2520%28%2520rank%252C%2520%28%2520int%2520%29%2520pige.size%2520%28%2520%29%2520%252B%25201%2520%29%253B%250A%2509%2509%250A%2509%2509if%2520%28%2520pige.size%2520%28%2520%29%2520%2526%2526%2520pige.top%2520%28%2520%29%2520%253C%253D%2520t%2520%29%250A%2509%2509%2509t%2520-%253D%2520pige.top%2520%28%2520%29%252C%2520pige.pop%2520%28%2520%29%253B%250A%2509%2509else%2520break%253B%250A%2509%2509%250A%2509%257D%250A%2509%250A%2509printf%2520%28%2520%2522%2525d%2522%252C%2520rank%2520%29%253B%250A%2509%250A%2509return%25200%253B%250A%2509%250A%257D" style="width: 926px; height: 1108px; border: 0; transform: scale(1); overflow: hidden"> </iframe>

CF229B Planets

Code

<iframe sandbox="allow-scripts allow-same-origin" src="https://carbon.vercel.app/embed?bg=rgba%28255%2C255%2C255%2C0%29&t=one-dark&wt=none&l=text%2Fx-c%2B%2Bsrc&ds=true&dsyoff=0px&dsblur=26px&wc=true&wa=true&pv=37px&ph=38px&ln=true&fl=1&fm=Fira+Code&fs=14.5px&lh=116%25&si=false&es=4x&wm=false&code=%252F%252F%2520Problem%253A%2520CF229B%2520Planets%250A%252F%252F%2520URL%253A%2520https%253A%252F%252Fwww.luogu.com.cn%252Fproblem%252FCF229B%250A%252F%252F%2520Memory%2520Limit%253A%2520250%2520MB%250A%252F%252F%2520Time%2520Limit%253A%25202000%2520ms%250A%252F%252F%2520Author%253A%2520arlenWKX%250A%250A%2523%2520include%2520%253Cbits%252Fstdc%252B%252B.h%253E%250A%250Ausing%2520namespace%2520std%253B%250A%250Aconst%2520int%2520N%2520%253D%25201e5%2520%252B%25205%253B%250Aconst%2520int%2520WTF%2520%253D%25201.5e9%253B%250A%250Aint%2520n%252C%2520m%252C%2520a%252C%2520b%252C%2520c%253B%250Aset%2520%253C%2520int%2520%253E%2520s%2520%255B%2520N%2520%255D%253B%250Aint%2520had%2520%255B%2520N%2520%255D%252C%2520nxt%2520%255B%2520N%2520%252B%2520N%2520%255D%252C%2520vct%2520%255B%2520N%2520%252B%2520N%2520%255D%252C%2520len%2520%255B%2520N%2520%252B%2520N%2520%255D%252C%2520edgenum%253B%250Apriority_queue%2520%253C%2520pair%2520%253C%2520int%252C%2520int%2520%253E%2520%253E%2520q%253B%250Aint%2520dis%2520%255B%2520N%2520%255D%253B%250A%250Avoid%2520addedge%2520%28%2520int%2520u%252C%2520int%2520v%252C%2520int%2520w%2520%29%250A%257B%250A%2509%250A%2509edgenum%2520%252B%252B%253B%250A%2509%250A%2509nxt%2520%255B%2520edgenum%2520%255D%2520%253D%2520had%2520%255B%2520u%2520%255D%253B%250A%2509vct%2520%255B%2520edgenum%2520%255D%2520%253D%2520v%253B%250A%2509len%2520%255B%2520edgenum%2520%255D%2520%253D%2520w%253B%250A%2509had%2520%255B%2520u%2520%255D%2520%253D%2520edgenum%253B%250A%2509%250A%257D%250A%250Aint%2520main%2520%28%2520%29%250A%257B%250A%2509%250A%2509scanf%2520%28%2520%2522%2525d%2525d%2522%252C%2520%2526%2520n%252C%2520%2526m%2520%29%253B%250A%2509%250A%2509for%2520%28%2520int%2520i%2520%253D%25201%253B%2520i%2520%253C%253D%2520m%253B%2520i%2520%252B%252B%2520%29%250A%2509%257B%250A%2509%2509%250A%2509%2509scanf%2520%28%2520%2522%2525d%2525d%2525d%2522%252C%2520%2526%2520a%252C%2520%2526%2520b%252C%2520%2526%2520c%2520%29%253B%250A%2509%2509%250A%2509%2509addedge%2520%28%2520a%252C%2520b%252C%2520c%2520%29%253B%250A%2509%2509addedge%2520%28%2520b%252C%2520a%252C%2520c%2520%29%253B%250A%2509%2509%250A%2509%257D%250A%2509%250A%2509for%2520%28%2520int%2520i%2520%253D%25201%253B%2520i%2520%253C%253D%2520n%253B%2520i%2520%252B%252B%2520%29%250A%2509%257B%250A%2509%2509%250A%2509%2509scanf%2520%28%2520%2522%2525d%2522%252C%2520%2526%2520a%2520%29%253B%250A%2509%2509%250A%2509%2509while%2520%28%2520a%2520--%2520%29%250A%2509%2509%2509scanf%2520%28%2520%2522%2525d%2522%252C%2520%2526%2520b%2520%29%252C%2520s%2520%255B%2520i%2520%255D.insert%2520%28%2520b%2520%29%253B%250A%2509%2509%2509%250A%2509%257D%250A%2509%250A%2509for%2520%28%2520int%2520i%2520%253D%25201%253B%2520i%2520%253C%253D%2520n%253B%2520i%2520%252B%252B%2520%29%2520dis%2520%255B%2520i%2520%255D%2520%253D%2520WTF%253B%250A%2509%250A%2509dis%2520%255B%25201%2520%255D%2520%253D%25200%253B%250A%2509q.push%2520%28%2520make_pair%2520%28%25201%252C%25200%2520%29%2520%29%253B%250A%2509%250A%2509while%2520%28%2520%21q.empty%2520%28%2520%29%2520%29%250A%2509%257B%250A%2509%2509%250A%2509%2509int%2520u%2520%253D%2520q.top%2520%28%2520%29.first%252C%2520t%2520%253D%2520-%2520q.top%2520%28%2520%29.second%253B%2520q.pop%2520%28%2520%29%253B%250A%2509%2509%250A%2509%2509if%2520%28%2520dis%2520%255B%2520u%2520%255D%2520%21%253D%2520t%2520%29%2520continue%253B%250A%2509%2509%250A%2509%2509while%2520%28%2520s%2520%255B%2520u%2520%255D.count%2520%28%2520t%2520%29%2520%29%2520t%2520%252B%252B%253B%250A%2509%2509%250A%2509%2509for%2520%28%2520int%2520e%2520%253D%2520had%2520%255B%2520u%2520%255D%253B%2520e%253B%2520e%2520%253D%2520nxt%2520%255B%2520e%2520%255D%2520%29%250A%2509%2509%257B%250A%2509%2509%2509%250A%2509%2509%2509int%2520v%2520%253D%2520vct%2520%255B%2520e%2520%255D%252C%2520w%2520%253D%2520len%2520%255B%2520e%2520%255D%253B%250A%2509%2509%2509%250A%2509%2509%2509if%2520%28%2520t%2520%252B%2520w%2520%253C%2520dis%2520%255B%2520v%2520%255D%2520%29%250A%2509%2509%2509%2509dis%2520%255B%2520v%2520%255D%2520%253D%2520t%2520%252B%2520w%252C%2520q.push%2520%28%2520make_pair%2520%28%2520v%252C%2520-%2520dis%2520%255B%2520v%2520%255D%2520%29%2520%29%253B%250A%2509%2509%2509%2509%250A%2509%2509%257D%250A%2509%2509%250A%2509%257D%250A%2509%250A%2509printf%2520%28%2520%2522%2525d%2522%252C%2520dis%2520%255B%2520n%2520%255D%2520%253D%253D%2520WTF%2520%253F%2520-1%2520%253A%2520dis%2520%255B%2520n%2520%255D%2520%29%253B%2520%250A%2509%250A%2509return%25200%253B%250A%2509%250A%257D" style="width: 816px; height: 1613px; border: 0; transform: scale(1); overflow: hidden"> </iframe>