Python3 解法, 执行用时: 518ms, 内存消耗: 23072K, 提交时间: 2021-06-22 20:53:51

import heapq
from operator import itemgetter
n=int(input())
heap=[]
test = [[0 for i in range(2)] for j in range(n)]
i=0
for i in range(n):
    a,b=map(int,input().split())
    test[i][0]=a
    test[i][1]=b
test.sort(key=itemgetter(0))
ans=0
t=0
for i in range(n):
    if t<test[i][0]:
        ans+=test[i][1]
        heapq.heappush(heap,test[i][1])
        t+=1
    else:
        w=heapq.heappop(heap)
        heapq.heappush(heap, w)
        if test[i][1]>=w and test[i][0]==t:
            heapq.heappop(heap)
            ans=ans+test[i][1]-w;
            heapq.heappush(heap, test[i][1])
print(ans)

C++14(g++5.4) 解法, 执行用时: 61ms, 内存消耗: 1784K, 提交时间: 2020-01-30 12:51:33

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int t,v;
}e[100005];
bool cmp(edge a,edge b){
    return a.t<b.t;
}
priority_queue<int,vector<int>,greater<int> >q;
int main(){
    int n;
    long long ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&e[i].t,&e[i].v);
    sort(e,e+n,cmp);
    for(int i=0;i<n;i++){
        if(e[i].t<=q.size()){
            if(e[i].v>q.top()) ans+=e[i].v-q.top(),q.pop(),q.push(e[i].v);
        }
        else ans+=e[i].v,q.push(e[i].v);
    }
    printf("%lld\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 75ms, 内存消耗: 1784K, 提交时间: 2020-02-26 17:37:48

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int now,n;
long long s;
priority_queue<int> q;
struct cow
{
	int s,v;
}c[100005];
bool cmp(cow a,cow b)
{
	return a.s<b.s;
}
void init()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	scanf("%d%d",&c[i].s,&c[i].v);
	sort(c+1,c+1+n,cmp);
}
void work()
{
	for(int i=1;i<=n;i++)
	{
		s+=c[i].v;
		now++;
		q.push(-c[i].v);
		if(now>c[i].s)
		s+=q.top(),q.pop(),now--;
	}
	printf("%lld\n",s);
}
int main()
{
	init();
	work();
	return 0;
}