题目地址

采用贪心的思想：

1：
按时间从小到大排序。让快过期的物品先卖，后面处理是否要卖它。
设我们已经按当前最优的情况选出来了t个，
当前处理的物品时间过期为t时，我们判断选出来的物品中是否有比它小的，如果有，则替换。
当前处理物品时间过期为>t时，我们直接加入。
故可以用堆去维护最小的那个。

2：
按利润从大到小的排序。我们尽可能在过期的时候去卖它。
对于一个物品，过期的时间为t,则我们尽量在t的时候去卖它，若当前t已经被预定了，则往前面找空位去卖。止于0。
可以用并查集去维护这句话（若当前t已经被预定了，则往前面找空位去卖。），即当确定一个物品在r的时间卖，则离他最近的一个空位为fa[r-1].

1代码：

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;const int INF = 0x3f3f3f3f;
const double eps = 1e-4;
const int mod = 999911659;
const int N = 1e6+10;int n;
vector<pii> ve;
priority_queue<int,vector<int>,greater<int> > pq;signed main(){IOS;#ifdef ddgofreopen("C:/Users/asus/Desktop/ddgoin.txt","r",stdin);#endifwhile(cin>>n){ve.clear();int p,t;for(int i=0;i<n;i++){cin>>p>>t;ve.push_back({t,p});}sort(ve.begin(),ve.end());for(int i=0;i<(int)ve.size();i++){int t = ve[i].first,p = ve[i].second;int si = pq.size();if(t > si) pq.push(p);else if(t == si && p > pq.top()) pq.pop(),pq.push(p);}int sum = 0;while(!pq.empty()){int t = pq.top();pq.pop();sum += t;}cout<<sum<<endl;}return 0;
}

2代码：

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;const int INF = 0x3f3f3f3f;
const double eps = 1e-4;
const int mod = 999911659;
const int N = 1e4+10;int n;
int fa[N];
int get(int x){if(x != fa[x]) fa[x] = get(fa[x]);return fa[x];
}struct Node{int p,t;bool operator <(const Node&T)const{return p > T.p;}
}node[N];signed main(){IOS;#ifdef ddgofreopen("C:/Users/asus/Desktop/ddgoin.txt","r",stdin);#endifwhile(cin>>n){for(int i=0;i<=1e4;i++) fa[i]  = i;for(int i=0;i<n;i++){int p,t;cin>>p>>t;node[i] = {p,t};}int sum = 0;sort(node,node+n);for(int i=0;i<n;i++){int p = node[i].p,t = node[i].t;int a = get(t);if(a != 0){int b = get(a-1);fa[a] = b;sum += p; }}cout<<sum<<endl;}return 0;
}