贪心问题的关键在于选择合适的贪心策略（局部最优解可以推导出全局最优解）
简单·简单的贪心
在黑板上写了N个正整数做成的一个数列，进行如下操作：
每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数。
在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。
这道题是用优先队列辅助实现贪心问题的一道典型题。
贪心和优先队列为什么能有不解之缘？ 其实仔细思考一下就会明白
开两个优先队列，每次取最小的两个操作一下把结果放进去，最后剩下就是max。每次取最大的两个操作一下把结果放进去，最后剩下的就是min。
什么？你要我证明。
那就来好了。
假设经（N－3）次变换后得到3个数：a,b,max’（max’≥a≥b），其中max’是（N－2）个数经（N－3）次变换后所得的最大值，此时有两种求值方式，设其所求值分别为x、y 则有：x＝（a×b＋1）×max’＋1，y＝（a×max’＋1）×b+1。所以x-y＝max’－b≥0若经（N－2）次变换后所得的3个数为：b（m≥a≥b）且m不为（N－2）次变换后的最大值，即m＜max’则此时所求得的最大值为：＝（a×b+1）×m+1 此时 － ＝（1+ab）（max’－m）＞0 所以此时不为最优解。
所以若使第k（1≤k≤N－1）次变换后所得值最大，必使（k－1）次变换后所得值最大（符合贪心策略的特点2），在进行第k次变换时，只需取在进行（k－1）次变换后所得数列中的两最小数p，q施加f操作：p←p×q+1，q←∞即可，因此此题可用贪心策略求解。讨论完毕。
在求min时，我们只需在每次变换的数列中找到两个最大数p，q进行变换：p←p×q+1，q←-∞即可。原理同上。
#include <iostream> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int maxlen=25; int ar[maxlen]; int main(){ int n,i,j,k,num1,num2,num3,min,max; while(~scanf("%d",&n)){ priority_queue< int,vector<int>,greater<int> > p; priority_queue< int,vector<int>,less<int> > q; while(p.empty() == false) p.pop(); while(q.empty() == false) q.pop(); for(i=1;i<=n;i++){ scanf("%d",&ar[i]); p.push(ar[i]); q.push(ar[i]); } while(p.size() >=2){ num1=p.top(); p.pop(); num2=p.top(); p.pop(); p.push(num1 * num2 + 1); } max=p.top(); while(q.size() >=2){ num1=q.top(); q.pop(); num2=q.top(); q.pop(); q.push(num1 * num2 + 1); } min=q.top(); printf("%d ",max-min); } return 0; }
AlvinZH的学霸养成记II
这道题，其实也是一道贪心+sort+优先队列的题。
我们可以设置一个curtime来作为一个扫描的指针，对于每门课程，如果可以学习的话（ curtime + last_time） <= ddl 那么就学习，否则的话，就用之前的最长时间的课程替换掉？为什么要替换其实就体现了贪心的思想，在同样的课程含量下，curtime越小那么。我们选择的余地就会越大。（局部最优解推导出全局最优解）
#include <iostream> #include <algorithm> #include <string.h> #include <queue> using namespace std; typedef struct mooc{ int d; int e; }course; //优先队列的使用 const int Maxlen=1e5 + 10; course ar[Maxlen]; bool cmp(course a,course b){ return a.e < b.e; } int main(){ int i,j,k,n,cur,ans; while(~scanf("%d",&n)){ for(i=0;i<n;i++) scanf("%d %d",&ar[i].d,&ar[i].e); sort(ar,ar+n,cmp); cur=0; ans=0; priority_queue<int> q; for(i=0;i<n;i++){ cur+=ar[i].d; q.push(ar[i].d); if(cur>ar[i].e){ cur-=q.top(); q.pop(); } else ans++; } printf("%d ",q.size()); } return 0; }
挑战神奇宝贝联盟
贪心+优先队列辅助实现
毒素多的应该尽早解决，故使用优先队列模拟即可。
#include <iostream> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int maxlen=1e5 + 10; int ar[maxlen]; int main(){ int n,i,j,k,t,num,temp; while(~scanf("%d",&n)){ priority_queue< int,vector<int> ,less<int> > q; for(i=1;i<=n;i++){ scanf("%d",&ar[i]); q.push(ar[i]); } scanf("%d",&k); t=0; while(q.size() > 0){ num=q.top(); q.pop(); num-=k; j=0; while(q.size() > 0){ temp=q.top(); q.pop(); temp-=1; ar[++j]=temp; } for(i=1;i<=j;i++) if(ar[i]>0) q.push(ar[i]); if(num>0) q.push(num); t++; } printf("%d ",t); } return 0; }