POJ 1456 贪心 并查集

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

struct s{
    int day, val;
}arr[100005];
bool cmp(s a, s b){
    if(a.day != b.day)
        return a.day > b.day;
    return a.val > b.val;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0){puts("0");continue;}
        priority_queue<int>Q;
        for(int i=0;i<n;i++)
            scanf("%d%d",&arr[i].val,&arr[i].day);
        sort(arr,arr+n,cmp);
        /// 注意 这里的排序是将日期大的放在了前面

        int cnt = arr[0].day,sum=0;
        /// 这里是暴力模拟每一天
        /// 假设从小到大模拟
        /// 第一天的物品价值较低
        /// 而第二天有两个物品的价值都较高
        /// 那么可以将第二天的一个物品安排到第一天
        /// 会发生冲突
        /// 而从大到小模拟的话
        /// 因为已经将日期在后面的安排完了
        /// 所以不会发生从后面来的冲突
        for(int i=0;cnt;cnt--){

            for(;i<n && cnt <= arr[i].day;i++){
                Q.push(arr[i].val);
            }
            if(!Q.empty())
                sum += Q.top(),Q.pop();
        }
        printf("%d\n",sum);
    }
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct s{
    int d, p;
}arr[10010];
int pre[10010];
bool cmp(s a,s b){
    return a.p > b.p;
}
int find_(int x){
    if(pre[x] == -1)
        return x;
    return pre[x] = find_(pre[x]);
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        memset(pre,-1,sizeof(pre));
        for(int i=0;i<n;i++)
            scanf("%d%d",&arr[i].p,&arr[i].d);
        sort(arr,arr+n,cmp);
        int ans = 0;
        for(int i=0;i<n;i++){
            int t = find_(arr[i].d);
            if(t>0){
                ans += arr[i].p;
                pre[t] = t-1;
            }
        }
        printf("%d\n",ans);
    }

    return 0;
}