本文共 8551 字，大约阅读时间需要 28 分钟。
一往直前！贪心法
贪心就是套方案或者数学证明呗，题做多了就有感觉了。
贪心法的证明大致有3种：
- 反证法
- 数学归纳（比如，先列举一个最简单的情况，如果有大小关系，我们可以交换两个项，把结果的大小进行比较）
- A>=B且A<=B则A=B.我们一般把A当做我们的贪心解法，B当做最优解，显然A<=B，我们只需要证明A>=B即可。
贪心中真的很多排序，堆，pair，结构体，要想清楚他们维护的是什么，考验的是基础的代码实现逻辑和双指针算法等。还有很多边界问题，比如前导0，相等，奇偶数…
书上的题：
区间调度问题： 这个我们都知道，选结束时间最早的嘛。
因为是对结束区间排序，我们把结束端点放进pair的first里，开始端点放在pair的second里。
pair p[N];void solve(){ sort(p,p+n); int t=p[0].first; for(int i=1;i t) { p[i].first=t; ans++; } }}
字典序最小问题
这题重要在对于一些特殊值，比如边界，相等的情况的处理。
这题的贪心策略是将S与S翻转过的字符串比较（不是真翻转，就是用指针倒着数即可），因为当头字符和尾字符相等，我们必须比较去掉他们后的下一个字符再做定论。
void solve(){ int i=0,j=n-1; while(i<=j) { bool flag=0; for(int k=0;k s[b-k]) { flag=0; break; } if(a[a+k] Saruman’s Army
这个策略也很简单，我们先找到能覆盖当前点的最小点，再找到这个点能覆盖到的最右边的点。如此循环。
void solve(){ sort(a,a+n); int i=0,ans=0; while(i Fence Repair
这是一道经典的合并果子。。。
（合并果子等会会写到）
谈谈贪心的常用方式
贪心会与二分值的验证结合
洛谷的贪心题单（只做了提高组）
P2240部分背包问题 这根本不是个背包好吧，当然是先放单位重量价格最高的啦0v-
另外注意浮点数，不要直接比大小。
#include using namespace std;const int N=1010;double w[N],v[N]; pair a[N];int main(){ int n; double t; cin>>n>>t; for(int i=0;i >w[i]>>v[i]; a[i].first=w[i]/v[i]; a[i].second=i; } double sum=0,res=0; sort(a,a+n); for(int i=0;i
P1090合并果子
#include using namespace std;const int N=10100;int a[N];priority_queue q;int main(){ int n; cin>>n; for(int i=0;i >a[i]; q.push(-a[i]); } int res=0,x1,x2; while(q.size()!=1) { x1=q.top(); q.pop(); x2=q.top(); q.pop(); res=res-x1-x2; q.push(x1+x2); } cout<
P1106删数问题
这道题想出贪心策略后还要考虑两点：
- 如果全删了，要输出0。
- 边界：如果最后遍历到i=n-k了，后面的直接全删掉。
#include using namespace std;int a[500];int main(){ string m; cin>>m; int k; cin>>k; int t=1; int flag=0,cnt=0; for(int i=1;i<=m.length();i++) { a[i]=m[i-1]-'0'; } int rest=m.length()-k; while(cnt
P4995跳跳！
我是把他想成了一根直线，从一端跳到另一端可以用双指针。
#include using namespace std;const int N=310;long long h[310];int main(){ int n; cin>>n; for(int i=0;i >h[i]; } sort(h,h+n); long long res=0; if(h[n-1]>(-h[0])||h[0]>=0) { res+=h[n-1]*h[n-1]; reverse(h,h+n); } else { res+=h[0]*h[0]; } int i=0,j=n-1; if(n%2==0) { while(i-j!=1) { res=res+(h[i]-h[j])*(h[i]-h[j]); i++; res=res+(h[i]-h[j])*(h[i]-h[j]); j--; } } else { while(i!=j) { res=res+(h[i]-h[j])*(h[i]-h[j]); i++; res=res+(h[i]-h[j])*(h[i]-h[j]); j--; } } if(i==j-1) { res+=(h[i]-h[j])*(h[i]-h[j]); } cout<
P4447 分组
可以暴力枚举每个数加在哪个后面，但是是O(n
2)的
用堆维护最小值可以到O(nlogn)
对于每个序列，如果接不上了就可以从堆中丢弃，并取得长度最小值，如果接的上就接上去。
#include using namespace std;const int N=1e5+10;int a[N];priority_queue > pq;int minn=INT_MAX;int main(){ int n; cin>>n; for(int i=0;i >a[i]; } sort(a,a+n); for(int i=0;i 1-pq.top().first) { //cout< <<" "<<1-pq.top().first< < x=pq.top(); pq.pop(); x.second--; x.first--; pq.push(x); } while(!pq.empty()) { minn=min(minn,-pq.top().second); pq.pop(); } cout<
P1080 国王游戏
涉及难点：贪心性质的证明和高精度乘除法
对于贪心性质的证明：我们先看一题这道题的加减法版本
耍杂技的牛 这题是对w+s排序，也不需要用到高精度
#include #include using namespace std;const int N=100010;pair a[N];int w;int s;int main(){ int n; cin>>n; for(int i=0;i >w>>s; a[i].first=w+s; a[i].second=s; } sort(a,a+n); int sum=0; int res=-100000000; for(int i=0;i
思路：见
简单的说就是交换两项，看看他们的最大值有没有变化。当然这个证明基于你已经有贪心思路的情况下。
对于高精度套板就行
乘法：令t=a[i]*b,把t%10的结果留下来，把t/10的结果进位
除法：与列竖式一样的，不断借位
最后如果有多余的进位也放进vector里，把t/b留下来，t%b继续借位除
注意把结果反过来pop前导零，或者做一个标记标记前导零
另外，我们直接用的反向的数字vector进行操作，要注意各个模板的变化。
#include using namespace std;const int N=1010;int a[N];int b[N];pair p[N]; vector mul(vector a,int b){ vector v; int t=0; for(int i=0;i
c; bool is_first = true; for (int i = a.size() - 1, t = 0; i >= 0; i -- ) { t = t * 10 + a[i]; int x = t / b; if (!is_first || x) { is_first = false; c.push_back(x); } t %= b; } reverse(c.begin(), c.end()); return c;}*/vector
v; int r=0; for(int i=a.size()-1;i>=0;i--) { r=r*10+a[i]; v.push_back(r/b); r=r%b; } reverse(v.begin(),v.end()); while(v.size()>1&&v.back()==0) { v.pop_back(); } return v;}vector