题目描述
约翰有太多的工作要做。为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。 他的工作日从0时刻开始，有10^8个单位时间。在任一时刻，他都可以选择编号1~N的N(1 <= N <= 10^6)项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。 对于第i个工作，有一个截止时间D_i(1 <= D_i <= 10^9)，如果他可以完成这个工作，那么他可以获利P_i( 1<=P_i<=10^9 ). 在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少.
输入输出格式
输入格式：
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains two space-separated integers: D_i and P_i
输出格式：
* Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.
输入输出样例
说明
Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).
Solution
这道题我一开始是往DP方向想的,结果尴尬地发现自己不造怎么定义状态... 于是就想贪心水分.
结果想了一个自己觉得是正解的贪心做法.然后发现只得了33分...
又调了良久,还是33分.
然后一看题解,发现题解只不过是把我的思路倒过来. 然后就对了.很显然我还是太菜了.
这道题的贪心的策略就是：
先把所有的价值都加进去.然后同步统计一个now统计时间.
如果当前时间已经超过了实现,那么我们就减掉价值最小的.
然后这个价值最小的用一个堆就可以维护.
代码
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=100008; struct sj{ ll d; ll p; }a[maxn]; priority_queue <int> q; ll read() { char ch=getchar(); ll f=1,w=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();} return f*w; } bool cmp(sj s,sj j){if(s.d!=j.d)return s.d<j.d;else return s.p<j.p;} ll ans,maxt,n; ll num,maxs[maxn]; int main() { n=read(); for(int i=1;i<=n;i++) a[i].d=read(),a[i].p=read(); sort(a+1,a+n+1,cmp); ll old=0; int now=0; for(int i=1;i<=n;i++) { ans+=a[i].p; now++; q.push(-a[i].p); //大根堆转小根堆 if(now>a[i].d) { ans+=q.top(),q.pop();now--; } } cout<<ans<<endl; }
然后 这是我的错误贪心：
for(int i=n;i>=0;i--) { if(a[i].d!=old) { ll tt=old-a[i].d; old=a[i].d; while(tt!=0) { int t=q.top(); q.pop(); ans+=a[t].p; tt--; } } q.push(i); }