CSU-ACM2018寒假集训比赛1B C

CSU-ACM2018寒假集训比赛1B C - Contest Balloons

本文主要是介绍CSU-ACM2018寒假集训比赛1B C - Contest Balloons，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

优先队列 / 重载运算符

1、按每支队伍的气球数从大到小排序

2、将气球数比Limak多的队伍加入优先队列

优先队列按队伍重量与气球数的差值从小到大排序

此处需用到重载运算符

3、判断是否能让队首上天，

能，则让他上天，Limak减去相应气球数，继续第2步骤

不能，则得到答案

代码：

#include <algorithm>
#include <iostream>
#include <string>
#include <cstdio>
#include <queue>
#include <cmath>using namespace std;struct node
{long long num,wig;bool operator < (const node & a) const{return wig - num > a.wig - a.num;}
}s[333333],k;bool judge (node a,node b){return a.num > b.num;}priority_queue <node> que;int main ()
{int n;scanf ("%d",&n);scanf ("%lld%lld",&k.num,&k.wig);for (int i=1;i<n;i++){scanf ("%lld%lld",&s[i].num,&s[i].wig);if (s[i].num > s[i].wig){i--;n--;}}sort (s+1,s+n,judge);int o=1,cnt=1;bool flag = true;while (o < n && s[o].num > k.num){//cout<<"in  "<<s[o].num<<" "<<s[o].wig<<" "<<k.num<<endl;cnt ++;que.push (s[o]);o ++;}int ans = cnt;while (!que.empty() && flag){long long tmp = que.top().wig - que.top().num + 1;if (k.num >= tmp){//cout<<"out "<<que.top().num<<" "<<que.top().wig<<" "<<k.num<<endl;k.num -= tmp;cnt --;que.pop();}elseflag = false;while (o < n && s[o].num > k.num){//cout<<"in  "<<s[o].num<<" "<<s[o].wig<<" "<<k.num<<endl;cnt ++;que.push (s[o]);o ++;}ans = min (ans,cnt);}printf ("%d\n",ans);return 0;
}

e.g. ~~gai中国有嘻哈的歌怎么都没了~~