code1052 地鼠游戏

贪心算法，从后往前

来自codevs的题解：

我的纠结思考过程：
如果每一秒都没有重复的地鼠出现那么肯定是一个一个挨着打
如果有重复的地鼠那么要考虑打那个更优当然是选分值最大的

单纯这样想很合理但是忽略了一种情况分值小的地鼠早出现了而后面重复的地鼠都比这个早出现的地鼠分值大
我们就不能去打这只小的而是把时间去用在打后面重复的地鼠身上
如 1 2 2
5 6 7

那么按照地鼠的分值排序然后挨着打怎么样
也不对因为分值大的地鼠也有可能停留时间长我们早打了他会导致时间短的地鼠没法打而时间还空着无视可做
如 2 1
9 5

后来看了题解才明白
把上述两种错误的思想结合起来就是把正解
我们倒着枚举时间打地鼠这样就避免了第二种情况的错误
然后再从所有地鼠中选出能打的分值最大的这样就避免了第一种情况的错误

设立一个大顶堆，堆中的元素是当前时间下能打的地鼠的分值
把地鼠们按照消失的时间由大到小排序，循环时间temp=最后消失的地鼠的消失时间 to 1
把所有消失时间等于temp的地鼠放入堆（表示可以打它们了）
然后取出最大的（堆顶）打掉，累加得分即可

代码如下：

#include<iostream>

#include<algorithm>

#include<queue>

#define Size 105

using namespace std;

int n;

struct Mouse{

    int t,w;

}mouse[Size];

priority_queue<int> q;

bool cnt(Mouse m1,Mouse m2){return m1.t>m2.t;} 

int main(){

    cin>>n;

    for(int i=;i<=n;i++){

        cin>>mouse[i].t;

    }

    for(int i=;i<=n;i++){

        cin>>mouse[i].w;

    }

    sort(mouse+,mouse+n+,cnt);

    int ans=;

    for(int temp=mouse[].t,k=;temp>;temp--){

        while(mouse[k].t==temp){

            q.push(mouse[k].w);

            k++;

        }

        if(!q.empty()){

            ans+=q.top();

            q.pop();

        }

    }

    cout<<ans<<endl;

    return ;

}

巴特西

code1052 地鼠游戏

最新文章

热门文章