【题目描述】

XY在玩一个包含N个任务的游戏。每个任务完成时限为Ti（你可以认为还没开始做任务时的时间为0），奖励为Wi。由于XY技术的娴熟以及任务的简单，对于每个任务，他都可以在一个单位时间内完成。

XY想要知道他能够获得的最多的奖励。

【输入】

第一行一个整数N，表示需要完成的任务数目。

接下来N行，每行两个整数T、W，分别表示完成这个任务的最后期限和完成这个任务后获得的奖励。

【输出】

输出数据有且仅有一行，只包含一个整数，表示最多获得的奖励。

【输入样例】

2
1 5
1 4

【输出样例】

5

【样例输入2】

5
2 3
1 2
4 5
1 3
3 4

【样例输出2】

15

【样例解释2】

对于样例2，XY可以选择完成任务1、3、4 和5，这样他可以获得奖励15。

【数据规模及约定】

对于10%的数据，N≤100，Ti≤100，Wi≤2000。

对于30%的数据，N≤1000，Ti≤5000，Wi≤2000。

对于50%的数据，N≤10000，Ti≤20000，Wi≤2000。

对于100%的数据，N≤200000，Ti≤200000，Wi≤2000。

思路

首先考虑贪心
1.我们首先需要完成获利大的任务(所以排序)
2.完成任务时尽量安排晚一点完成（为其他任务留时间，所以从最晚时间点向前找）

所以贪心裸代码如下

#include<bits/stdc++.h>
using namespace std;
struct oppo{
    int s,w;
}e[1000006];
bool rule(oppo a,oppo b)
{
    return a.w>b.w;
}
int n,ans;
bool f[200005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>e[i].s>>e[i].w;
    sort(e+1,e+n+1,rule);
    for(int i=1;i<=n;i++)
    {
        for(int j=e[i].s;j>=1;j--)
            if(!f[j])
            {
                ans+=e[i].w;
                f[j]=1;
                break;
            }
    }
    cout<<ans<<endl;
    return 0;
}

交上去，完美超时
什么原因呢？
你看这个东西

    for(int i=1;i<=n;i++)
    {
        for(int j=e[i].s;j>=1;j--)
            if(!f[j])
            {
                ans+=e[i].w;
                f[j]=1;
                break;
            }
    }

这复杂度T飞了好吧
所以我们考虑路径压缩
AC代码如下

#include<bits/stdc++.h>
using namespace std;
struct oppo{
    int s,w;
}e[1000006];
bool rule(oppo a,oppo b)
{
    return a.w>b.w;
}
int n,ans;
int f[200005];
int main()
{
    cin>>n;
    for(int i=0;i<=200000;i++)
        f[i]=i-1;
    for(int i=1;i<=n;i++)
        cin>>e[i].s>>e[i].w;
    sort(e+1,e+n+1,rule);
    for(int i=1;i<=n;i++)
        if(f[e[i].s]!=-1){
            f[e[i].s]=f[f[e[i].s]];
            ans+=e[i].w;
        }
    cout<<ans<<endl;
    return 0;
}