郭大侠与Rabi-Ribi (优先队列)-LMLPHP

最近郭大侠迷上了玩Rabi-Ribi这个游戏。

Rabi-Ribi呢,是一个打兔子的动作冒险游戏,萌萌哒的兔子在地上跑来跑去,好萌好萌呀~

这个游戏是这样玩的,郭大侠作为一个主角,拿着一个小锤子,他的目标是敲晕兔子,然后最后把这些敲晕的兔子都带回家。

当然咯,郭大侠想带回的兔子的总价值最高~

但是,兔子实在是太多了,郭大侠的锤子每一秒钟只能敲晕一只兔子,而且每一只兔子只会在地面上逗留a[i]秒,在a[i]秒之后,这一只兔子就会跑回自己的小窝里面。

所以郭大侠面临一些抉择,希望你能帮助他。

Input

第一行包含一个整数N表示有N个兔子在地上跑来跑去。

第二行NN个用空格分隔的整数a[i]表示第i只兔子冒出后停留的时间

第三行NN个用空格分隔的整数v[i]表示第i只兔子的价值。

1≤N≤100000

1≤a[i]≤5000

1≤v[i]≤1000

Output

输出郭大侠最多能获得的价值是多少

Sample Input

5
5 3 6 1 4
7 9 2 1 5

3
1 1 1
1 2 3

Sample Output

24

3

Hint

死宅真可怕,连可爱的兔子都要敲晕带回家 QAQ

//一眼看去貌似十分简单,随手写了已发wa了才,重新认识到这题!

因为每秒可以敲一只兔子,所以,将兔子按时间排序,然后,要使每秒可以创造的价值足够大,所以,就是选t只最大价值的兔子即可

 #include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define MX 100005
struct Tu
{
int t,v;
bool operator < (const Tu& b)const
{
return t<b.t;
}
}tu[MX]; int main()
{
int n;
scanf("%d",&n);
for (int i=;i<n;i++)
scanf("%d",&tu[i].t);
for (int i=;i<n;i++)
scanf("%d",&tu[i].v);
sort(tu,tu+n);
priority_queue<int ,vector<int>,greater<int> > Q;
for (int i=;i<n;i++)
{
if (tu[i].t>Q.size())
{
Q.push(tu[i].v);
}
else
{
Q.push(tu[i].v);
Q.pop();
}
}
int ans = ;
while (!Q.empty()) ans+=Q.top(),Q.pop();
printf("%d\n",ans);
return ;
}
05-13 08:01