题面

疯狂的小金
Time Limit: 1000MS Memory limit: 65536K

题目描述
自从听说小白和小黑的友谊的小船翻了以后，小金很是开心，就和小白建立了小船，但是现在小金看到天上的n只小鸟，就萌生了一个疯狂的想法，他决定带着小白去打鸟，所以小金去商店买装备--->箭，现在他知道每只鸟的防御力，和每一只箭的攻击力和价值。如果箭的攻击力小于鸟的防御了，小鸟是不会被打下来的。最为奇葩的是每种箭只有一只，小金想将小鸟都打下来，如果不能那么小金和小白的小船又要翻啦。当然小金的资金最近比较的紧张，所以他想花费最小的钱。

输入
多组输入，每组第一行输入两个数n,m(1<=n,m<=50000)，表示小鸟的数量和箭的数量。接下来的一行的n个数表示每一个小鸟的防御力，接下来的m行，每行两个数，表示箭的攻击力v价值w,(1<=v,w<=100000).

输出
如果小金不能将所有的小鸟射下来，输出"No Solution"。否则输出最小的花费。

示例输入
3 3
1 2 3
2 1
3 2
4 3

示例输出
6

提示

来源
“师创杯”山东理工大学第八届ACM程序设计竞赛

解题思路

显而易见的贪心题。只需要将鸟的防御力按从高到低排序，将箭按攻击力从高到底排序。然后遍历所有的鸟，每一轮将所有能够射杀此鸟的箭都收进一个表示当前可用弓箭的数组中，然后在当前此数组中寻找一支价值最小的箭来射杀此鸟，并将该箭从数组中移除。这样我们的贪心策略即是对于每一只鸟，选取当前可用弓箭中价值最小的箭，保证了每一步都是最优方案。
不过这题由于数据量很大，而且每一轮循环都要涉及加入若干元素、重新排序、删除价值最小元素等操作，所以很容易超时。当时校赛也是 vector, set 都试了，最后换到优先队列才过。

这样我们就可以写出本题的代码了：

#include <cstdio>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;

struct info {
    int v, w;
    bool operator < (const info & cmp) const {
        return v > cmp.v;
    }
} a[50000];

int main(int argc, char const *argv[]) {
    int n, m, d[50000];
    while(~ scanf("%d %d", &n, &m)) {
        for(int i=0; i<n; ++i) {
            scanf("%d", &d[i]);
        }
        for(int i=0; i<m; ++i) {
            scanf("%d %d", &a[i].v, &a[i].w);
        }
        if(n > m) {
            printf("No Solution\n");
            continue;
        }
        sort(d, d+n, greater<int>());
        sort(a, a+m);
        priority_queue<int, vector<int>, greater<int> > q;
        bool ok = true;
        long long ans = 0;
        for(int i=0, j=0; i<n; ++i) {
            for(; j<m; ++j) {    //把剩余弓箭中可以射杀该鸟的箭都加入到队列中
                if(a[j].v >= d[i]) q.push(a[j].w);
                else break;
            }
            if(!q.empty()) {
                ans += q.top();    //用队首的箭（即价值最小的箭）射杀该鸟
                q.pop();
            }
            else {    //如果此鸟无箭可杀，则无解
                ok = false;
                break;
            }
        }
        if(ok) printf("%lld\n", ans);
        else printf("No Solution\n");
    }
    
    return 0;
}