HDU-4544 湫湫系列故事——消灭兔子 (贪心+优先队列)

题目思路

将兔子的血量从大到小排列，将箭的属性写在类中（结构体也成），排序按照伤害从大到小排列，若有相等的则按价格从小到大排。

代码

#include<bits/stdc++.h>

using namespace std;

int N, M;

const int maxn = 100000+10;

int b[maxn], d[maxn], p[maxn];

class Arrow

{

public:

    int D, P;

    Arrow(int i, int j):D(i), P(j){}

    Arrow(){}

}a[maxn];

bool cmp(Arrow s1, Arrow s2)

{

    if(s1.D == s2.D)

        return s1.P < s2.P;

    return s1.D > s2.D;

}

int main()

{

    std::ios::sync_with_stdio(false);

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    while(cin >> N >> M)

    {

        memset(b, 0, sizeof(b));

        memset(d, 0, sizeof(d));

        memset(p, 0, sizeof(p));

        for(int i = 0; i < N; i++)

            cin >> b[i];

        for(int i = 0; i < M; i++)

        {

            cin >> d[i];

            a[i].D = d[i];

        }

        for(int i = 0; i < M; i++)

        {

            cin >> p[i];

            a[i].P = p[i];

        }

        sort(b, b + N, greater<int>());

        sort(a, a + M, cmp);

        priority_queue<int, vector<int>, greater<int> > q;

        long long ans = 0;

        int k = 0, flag = 0;

        for(int i = 0; i < N; i++)

        {

            while(k < M && b[i] <= a[k].D)

            {

                q.push(a[k].P);

                k++;

            }

            if(q.empty())

            {

                flag = 1;

                break;

            }

            ans += q.top();     //加上杀死该兔子对应的最佳方案

            q.pop();

        }

        if(flag)

            cout << "No" << endl;

        else

            cout << ans << endl;

    }

}

巴特西

HDU-4544 湫湫系列故事——消灭兔子 (贪心+优先队列)

题目思路

代码

最新文章

热门文章