开始一直想的是直接安时间-价值排序,然后从时间最少的开始for循环一遍找兔子,如果时间不够用则进入下一个时间段找兔子,然后就wa啊,后来想想有点不对,万一时间少的地方有比时间大的地方的兔子呢,所以这个地方要用一个优先队列来维护,和bzoj上面建筑抢修那个题一毛一样啊。


地址:http://acm.uestc.edu.cn/#/problem/show/1334


代码:

StatusAccepted
Time47ms
Memory1828kB
Length1696
LangC++


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
#defineFK(x) cout<<"Debug:---"<<x<<"---"<<endl
#define PAIR pair<int, int>
typedef long long LL;
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Node{
    int t, v;
    bool operator<(const Node &cmp) const{
        return t<cmp.t||(t==cmp.t&&v>cmp.v);
    }
}node[maxn];
int n;
priority_queue<int, vector<int>, greater<int> > all;
int main()
{
    while(~scanf("%d", &n)){
        for(int i=0;i<n;i++){
            scanf("%d", &node[i].t);
        }
        for(int i=0;i<n;i++){
            scanf("%d", &node[i].v);
        }
        sort(node, node+n);
        int ans=0,now=0;
        for(int i=0;i<n;i++){
            if(now+1<=node[i].t){
                all.push(node[i].v);
                now++;
            }
            else if(node[i].v>all.top()){
                all.pop();
                all.push(node[i].v);
            }
        }
        while(!all.empty()){
            ans+=all.top();
            all.pop();
        }
        printf("%d\n", ans);
    }
    return 0;
}