51nod-1191 消灭兔子(贪心)

记录一个菜逼的成长。。

题目链接

这题是上题的进阶。
对于每支箭，我们要找到第一个血量大于伤害值的兔子的位置pos，那么我们把这只箭的伤害值设为pos-1的兔子的血量值
跟上题类似，从后往前贪心
将伤害值为当前兔子血量值的价格放入小顶堆，并且清空数组，因为血量可以相等，防止重复放入。
每次选取堆顶元素就可以了。
如果在消灭某一只兔子时堆为空时，那么说明没有弓箭可以消灭这只兔子，所以输出No Solution

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define cl(a,b) memset(a,b,sizeof(a))
typedef long long LL;
const int maxn = 100000 + 10;
int b[maxn];
vector<int>a[maxn];
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int mx = 0;
    for( int i = 1; i <= n; i++ )
        scanf("%d",b+i);
    sort(b+1,b+1+n);
    for( int i = 1; i <= m; i++ ){
        int x,y;
        scanf("%d%d",&x,&y);
        int pos = upper_bound(b+1,b+1+n,x) - b;
        x = b[pos-1];
        a[x].pb(y);
    }
    LL ans = 0;
    for( int i = n; i >= 1; i-- ){
        for( int j = 0; j < a[b[i]].size(); j++ ){
            q.push(a[b[i]][j]);
        }
        a[b[i]].clear();
        if(!q.empty())ans += (LL)q.top(),q.pop();
        else {puts("No Solution");return 0;}
    }
    printf("%lld\n",ans);
    return 0;
}