先把工作按照Deadline从小到大排序
然后按顺序取，deadline大于现在总用时就取，等于现在总用时就从前面已取的工作中找一个P最小的同它比较，取P较大的一个
用优先队列维护已取工作中P的最小值
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #define LL long long 5 using namespace std; 6 const int maxn=100010; 7 LL n,ans=0,t=0; 8 struct work{ 9 LL d,p; 10 }a[maxn]; 11 struct cmp1{ 12 bool operator() (const LL a,const LL b)const {return a>b;} 13 }; 14 priority_queue<int,vector<int>,cmp1>q; 15 void read(long long &k){ 16 int f=1; k=0; char c=getchar(); 17 while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 18 while ('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 19 k*=f; 20 } 21 bool cmp2(work a,work b){return a.d<b.d;} 22 int main(){ 23 read(n); 24 for (int i=1;i<=n;i++) read(a[i].d),read(a[i].p); 25 sort(a+1,a+n+1,cmp2); 26 for (int i=1;i<=n;i++){ 27 if (a[i].d>t) q.push(a[i].p),ans+=a[i].p,t++; 28 else{ 29 int x=q.top(); 30 if (x<a[i].p){ 31 q.pop(); q.push(a[i].p); 32 ans+=a[i].p-x; 33 } 34 } 35 } 36 printf("%lld\n",ans); 37 return 0; 38 } View Code
转载于:https://www.cnblogs.com/DriverLao/p/7692565.html
相关资源：数据结构—成绩单生成器