Description
飞船有一个防护罩，初始耐久度为0，每秒加一单位，给出n次导弹攻击，第i次攻击在第t[i]秒，攻击力d[i]，如果防护罩耐久不小于导弹的攻击力则飞船没事，但防护罩耐久会掉d[i]，否则gg，但是飞船上有炮，每炮可以毁掉任意导弹，问最少需要多少炮飞船不gg
Input
第一行一整数n表示导弹数量，之后n行每行两个整数t[i],d[i]表示该次攻击的时间和导弹的攻击力，保证t非减
(1<=n<=200000,1<=t[i],d[i]<=1e9)
Output
输出保证飞船安全的情况下大的最少炮数
Sample Input
3
3 2
5 4
6 3
Sample Output
1
Solution
贪心，当前累加伤害值不大于飞船耐久继续往下扫，否则不停拿出之前所有攻击中伤害值最大的用炮打，所以用一个优先队列来维护伤害即可
Code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 222222
int n,t[maxn],d[maxn];
priority_queue<int>que;
int main()
{
while(~scanf("%d",&n))
{
while(!que.empty())que.pop();
for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&d[i]);
ll sum=0;
int ans=0;
for(int i=1;i<=n;i++)
{
que.push(d[i]),sum+=d[i];
while(i<n&&t[i+1]==t[i])i++,que.push(d[i]),sum+=d[i];
while(sum>t[i]&&!que.empty())
{
int now=que.top();
que.pop();
sum-=now;
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}