本文主要是介绍@NOIP, @UPC 暑假训练 :打地鼠游戏 (贪心-优先队列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
K: 打地鼠游戏
时间限制: 1 Sec 内存限制: 128 MB
提交: 397 解决: 89
[提交] [状态] [讨论版] [命题人:admin]
题目描述
伟大的2320学长特别喜欢打地鼠游戏，这个游戏开始后，会在地板上冒出一些地鼠来，你可以用榔头去敲击这些地鼠，每个地鼠被敲击后，将会增加相应的游戏分值。可是，所有地鼠只会在地上出现一段时间（而且消失后再也不会出现），每个地鼠都在0时刻冒出，但停留的时间可能是不同的，而且每个地鼠被敲击后增加的游戏分值也可能是不同。
最近2320学长经常玩这个游戏，以至于敲击每个地鼠只要1秒。他在想如何敲击能使总分最大。
输入
输入包含3行，第一行包含一个整数n（1<=n<=100000）表示有n个地鼠从地上冒出来，第二行n个用空格分隔的整数表示每个地鼠冒出后停留的时间（Maxt<=50000），第三行n个用空格分隔的整数表示每个地鼠被敲击后会增加的分值v（v<=1000）。每行中第i个数都表示第i个地鼠的信息。
输出
输出只有一行一个整数，表示所能获得的最大游戏总分值。
样例输入
5 5 3 6 1 4 7 9 2 1 5
样例输出
24
提示
30%的数据保证n<=100, t<=500,v<=50
60%的数据保证 n<=10000,t<=3000,v<=500
100%的数据保证 n<=100000,t<=5000,v<=1000
思路:
先按照时间排序, 然后 维护一个 优先队列, (维护 V) 当遇到 某个等待时间 < 当前时间 时, 进行维护.
代码:
#include <bits/stdc++.h>
#include <stdlib.h>
#include <utility>
#define findx(x,b,n) lower_bound(b+1,b+1+n,x)-b
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
#define SHUT ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr);
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r#pragma comment(linker, "/STACK:1024000000,1024000000") // 扩栈
//next_permutation(a+1,a+x) 全排列
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())using namespace std;typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;const double PI=acos(-1.0);
const ll INF=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1e6+5;
const int MOD=1e9+7;
const int mod=1e9+7;
int dir[5][2]={0,1,0,-1,1,0,-1,0};inline void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){ x=1; y=0; d=a; }else{ ex_gcd(b,a%b,d,y,x); y-=x*(a/b);};}
inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll ans=exgcd(b,a%b,x,y);ll temp=x;x=y;y=temp-a/b*y;return ans;}
inline ll lcm(ll a,ll b){ return b/gcd(a,b)*a;}inline ll inv_exgcd(ll a,ll n){ll d,x,y;ex_gcd(a,n,d,x,y);return d==1?(x+n)%n:-1;}
inline ll inv1(ll b){return b==1?1:(MOD-MOD/b)*inv1(MOD%b)%MOD;}/*********************************head************************//** Author : siz*/struct node
{int x,y;
}a[maxn];int cmp(node a,node b)
{//if( a.x == b.x)// return a.y > b.y;return a.x<b.x;
}
int main()
{int n;scanf("%d",&n);rep(i,0,n){scanf("%d",&a[i].x);}rep(i,0,n){scanf("%d",&a[i].y);}ll ans = 0;sort(a,a+n,cmp);int now = 0;priority_queue<int,vector<int>,greater<int> >Q;rep(i,0,n){//cout<<now<<"=="<<a[i].x<<" | "<<a[i].y<<endl;if( now >= a[i].x){if(!Q.empty()&&(a[i].y > Q.top())){ans-= Q.top();Q.pop();ans+=a[i].y;Q.push(a[i].y);}}else{ans += a[i].y;Q.push(a[i].y);now++;}}printf("%lld\n",ans);return 0;
}
这篇关于@NOIP, @UPC 暑假训练 :打地鼠游戏 (贪心-优先队列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
