频道栏目
首页 > 资讯 > 其他 > 正文

编程开发习题:消灭兔子(贪心)

17-10-02        来源:[db:作者]  
收藏   我要投稿

编程开发习题:消灭兔子(贪心)。
思路:按照Q币升序排序,血量也是升序排序。先用Q币少的去打血量少的,当碰到一个兔子的血量比伤害要高的时候,可以选择曾经用过的伤害高的箭,和当前的箭对比一下两者能否替换,如果能替换就替换掉,不能替换就继续后找。不会实现反观大佬思路,实现起来就很容易了。
按照箭的伤害降序排序,血量也是降序,然后把伤害比血量高的箭都放到优先队列,选择花费最小的,把兔子射死。直到射死所有兔子或者队列空了。

#include 
using namespace std;

const int MAXN = 1e5+10;
struct node
{
    int d,p;
};
node ns[MAXN];
int B[MAXN];

struct compare
{
    bool operator()(const node& a, const node& b)
    {
        //原来这里要用大于号才能使优先队列是最小堆啊
        return a.p > b.p;
    }
};

bool cmp(const node& a, const node& b)
{
    return a.d > b.d;
}

int main()
{
    int n,m;
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 0; i < n; ++i)
        cin >> B[i];
    sort(B,B+n);
    for(int i = 0; i < m; ++i)
        cin >> ns[i].d >> ns[i].p;
    sort(ns,ns+m,cmp);
    priority_queue<>,compare> que;
    int j = 0;
    long long res = 0;
    for(int i = n-1; i >= 0; --i)
    {
        while(j < m && ns[j].d >= B[i])
        {
            que.push(ns[j]);
            ++j;
        }
        if(que.empty())
        {
            cout << "No Solution" <
        
   
相关TAG标签
上一篇:第三方接口功能动态配置信息需要提供一个重新缓存的按钮
下一篇:Android基础——XML数据的三种解析方式
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站