一开始思路弄错了，刚开始想的时候误把所有截止时间为2的不一定一定要在2的时候买，而是可以在1的时候买。
举个例子：
50 2 10 1 20 2 10 1 50+20
50 2 40 4 30 4 20 1 10 1 20+50+30+40
思路：用优先级队列，每次取价格最大的(如果价格相同，取截止时间最大的)。
然后往1~maxdx里加，首先看它截止时间上的位置是否已经存在其他物品，如果不存在，就加到该处。
如果存在，就往前判断，直到有一处空位没被占用，就加入到该位置。
后来网上看了一下，可以用并查集查找不冲突的时间点
不用并查集优化，110ms；用并查集后，63ms
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; const int maxn=10001; int n; int vis[maxn]; //若vis[i]=1，表示此处已经有物品，即有物品在i时刻卖出 int maxdx=0; //用于记录所有物品中最大的截止时间 int f[maxn]; struct Product{ int price,deadtime; bool operator <(const Product tmp) const{ if(price==tmp.price) return deadtime<tmp.deadtime; else return price<tmp.price; } }; void init(){ for(int i=0;i<=maxdx;i++){ f[i]=i; } } int find_root(int x){ if(f[x]!=x) f[x]=find_root(f[x]); return f[x]; } int main() { int p,d; int ans,counts; Product tmp; while(scanf("%d",&n)!=EOF){ priority_queue<Product> q; maxdx=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ scanf("%d%d",&p,&d); if(d>maxdx) maxdx=d; tmp.price=p; tmp.deadtime=d; q.push(tmp); } init(); ans=0; counts=0; //用于记录所卖的物品个数，如果个数为maxdx，表明1~maxdx中的所有时刻都已有物品在卖 while(counts<maxdx && !q.empty()){ tmp=q.top(); q.pop(); if(vis[tmp.deadtime]==0){ ans+=tmp.price; vis[tmp.deadtime]=1; f[tmp.deadtime]=tmp.deadtime-1; //刚开始这里忘写了，导致WA counts++; } else{ int t=tmp.deadtime; int pos=find_root(t); if(pos>0){ vis[pos]=1; counts++; ans+=tmp.price; f[pos]=pos-1; } /* while(vis[t]==1){ t--; } if(t>0){ vis[t]=1; ans+=tmp.price; counts++; } */ } } printf("%d ",ans); } return 0; }