Supermarket（并查集）

考虑利润从高到底排序，优先把利润最高的填到最接近过期的空余位置
贪心证明：如果当前a[i]被填入而填入了比最靠近过期前面的位置显然不会更优，如果没有被填入而放了另一组方案利润更大，则把属于a[i]的位置换成a[i]一定更优，两者矛盾

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e4+10;
//注意有n条指令至多有2*n个点
int f[N<<1];
int find(int u)
{
    if(f[u] == u) return u;
    return f[u] = find(f[u]);
}
void merge(int u,int v)
{
    int f1 = find(u), f2 = find(v);
    if(f1 != f2) f[f1] = f2;
}
void solve()
{
    int n;
    while(cin>>n)
    {
        //过期天数不适合离散化，可能有两个3，一个1是可行的离散化后变成2和1就不行
        vector<PII> a(n);
        for(int i=0;i<n;++i) cin>>a[i].x>>a[i].y;
        for(int i=1;i<N;++i) f[i] = i;
        sort(a.rbegin(),a.rend());
        int res = 0;
        for(int i=0;i<n;++i)
        {
            //如果过期前还有空位的话
            //注意此处不应该是a[i].y和a[i].y-1连接而应该是a[i].y的根节点向左边连接
            if(find(a[i].y)>0) res += a[i].x, merge(f[a[i].y], f[a[i].y]-1);
        }
        cout<<res<<'\n';
    }
   
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}