[原创]51nod 1163 最高的奖励 [贪心]【杂类】

# include"stdio.h"  
# include"algorithm"  
# include"queue"  
using namespace std;  
const int maxn=5e4+5;  
struct task{  
    int times;  
    int cost;  
}t[maxn];  
bool cmp(const task a,const task b)  
{  
    if(a.times<b.times) return true;  
    return false;  
}  
int main()  
{  
    int n;  
    scanf("%d",&n);  
    for(int i=0;i<n;i++)  
    {  
        scanf("%d%d",&t[i].times,&t[i].cost);  
    }  
    sort(t,t+n,cmp);  
    priority_queue<int ,vector<int >,greater<int> >pq;  
    long long  ans=0;  
    for(int i=0;i<n;i++)  
    {  
        int k=t[i].cost;  
        if(t[i].times>pq.size()) //pq.size这里理解代表时间点  
        {  
            ans+=k;  
            pq.push(k);  
        }  
        else//时间点有冲突，把cost最小删除   
        {  
            ans+=k;  
            pq.push(k);  
            int minn=pq.top();  
            ans-=minn;  
            pq.pop();//删除   
        }      
    }  
    printf("%lld\n",ans);  
    return 0;  
}

struct node {
    int e,w;
}a[N];

bool cmp(node A,node B){
    //if(A.w==B.w)return A.e<B.e;
    return A.w>B.w;
}

int m[N];  //指针，指向距离当前时间点最近的没有做任务的时间点。
bool h[N]; //判断当前时间点有没有做任务。

int main(){
    int n;
    scanf("%d",&n);
    h[0]=1;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].e,&a[i].w);
        h[i]=0;
        m[i]=i;
    }
    sort(a+1,a+n+1,cmp);
    LL ans = 0;
    //lalal;
    for(int i=1;i<=n;i++){
        //printf("%d %d\n",a[i].e,a[i].w);

        int now = m[a[i].e];
        while(h[now]&&now>0){
            now = m[now-1]; //切记要减1
            //printf("%d %d   %d %d\n",now,m[now],h[now],h[m[now]]);
        }
        if(now<0)now=0;
        m[a[i].e]=now;

        if(!h[m[a[i].e]]){
            ans+=a[i].w;
            h[m[a[i].e]]=1;
            m[a[i].e]--;
            //printf("---\n");
        }

        //for(int i=1;i<=n;i++)  printf("%d%c",h[i],(i==n)?'\n':' ');
        //for(int i=1;i<=n;i++)  printf("%d%c",m[i],(i==n)?'\n':' ');
    }

    printf("%lld\n",ans);
    return 0;
}