C++14(g++5.4) 解法, 执行用时: 874ms, 内存消耗: 29796K, 提交时间: 2019-10-30 10:02:57

#include<iostream>
#include<cstring>
#include<cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch = 0;
    while(!isdigit(ch))
    {
        if(ch=='-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x*10+ch-'0';
        ch = getchar();
    }
    return x*f;
}
const int maxpd = 1e5+10;
int T,n;
struct Chicken
{
    int p,d;
    friend bool operator<(const Chicken &x,const Chicken &y)
    {
        return x.p<y.p;
    }
}ck[maxpd];
inline bool cmp(const Chicken &x,const Chicken &y)
{
    return x.d<y.d;
}
priority_queue<int> q2;
vector<int> pc[maxpd];
int main()
{
    long long ans;
    //priority_queue<Chicken> Q;

    int mx;
    T = read();
    while(T--)
    {
        n = read();
        ans = 0;
        mx = 0;
        //memset(ck,0,sizeof(ck));
        for(int i=1; i<=n; i++)
        {
            //ck[i].p = read();
            //ck[i].d = read();
            int a = read(), b = read();
            pc[b].push_back(a);
            mx = max(mx,b);
        }
        //sort(ck+1,ck+1+n,cmp);
        //int j=n;
        for(int i=mx,k=0; i>=1; i--)
        {
            /*
            while(ck[j].d>=i && j>0)
            {
                //Q.push(ck[j]);
                q2.push(ck[j].p);
                j--;

            }
            */
            for(int j=0; j<pc[i].size(); j++)
            {
                q2.push(pc[i][j]);
            }
            pc[i].clear();
            ///if(j<1+n-k)
            if(!q2.empty())
            {

                //ans += Q.top().p;
                ans += q2.top();
                //Q.pop();
                q2.pop();
                k++;
            }
        }
        printf("%lld\n",ans);
        //while(!Q.empty()) Q.pop();
        while(!q2.empty()) q2.pop();
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 789ms, 内存消耗: 1460K, 提交时间: 2020-11-13 20:26:22

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct ch{
	int p,d;
}a[maxn];
bool cmp(const ch &x, const ch &y){
	return x.d<y.d;
}
priority_queue<ch>q;
bool operator < (const ch &x, const ch &y){
	return x.p>y.p;
}
int main(){
	int t;scanf("%d",&t);
	while(t--){
		int n;scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d%d",&a[i].p,&a[i].d);
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;i++){
			if(a[i].d>q.size())q.push((ch){a[i].p,a[i].d});
			else {
				q.push((ch){a[i].p,a[i].d});
				q.pop();
			}
		}
		long long ans=0;
		while(q.empty()==false){
			ans+=q.top().p;
			q.pop();
		}
		printf("%lld\n",ans);
	}
	return 0;
}