一开始以为贪心算法很简单，“不就是从问题初始状态出发，依次选择最优选项吗”，后来发现真不简单。
贪心算法五个经典应用：
1、选择不相交区间问题（例题：活动安排）
题意：
给定n个开区间（a,b）,选择尽量多个区间，使得这些区间两两没有公共点。
做法：
将右端点从小到大排序，然后依次考虑每一个区间，如果后一个区间和前一个区间重合，不选。
例如绿线和蓝线和（1,2）区间的紫线冲突了。
例题：https://loj.ac/problem/10000
ac代码：
#include<bits/stdc++.h> using namespace std; struct node { int s,f; }; node a[1005]; int cmp(const node &a,const node &b) { return a.f<b.f; } int main() { int n,s,f; while(~scanf("%d",&n)) { memset(a,0,sizeof(a)); for(int i=0;i<n;i++) { scanf("%d%d",&a[i].s,&a[i].f); } sort(a,a+n,cmp); int cur = 0,sum = 1; for(int i=1;i<n;i++) { if(a[i].s>a[cur].f) { cur = i; sum++; } } printf("%d ",sum); } return 0; }
2、区间选点问题（例题：种树）
题意：
给定n个闭区间[a,b],在数轴上选择尽量少的点，使得每个区间内至少有m个点。
做法：
贪心策略，将每个区间的右端点从小到大排序，依次从每个区间的右端点向左端点做统计，统计当前共有多少点，如果数量不够，从右端向左端扫描画点，目的是使该点尽可能被后边的区间运用。
例题：https://loj.ac/problem/10001
AC代码：
#include <bits/stdc++.h> using namespace std; struct node { int s,e,t; }; bool book[30005]={0}; node a[5005]; int cmp(const node &a,const node &b){ return a.e<b.e; } int main(){ int h,n,b,e,t; scanf("%d",&n); scanf("%d",&h); int num = 0; for(int i = 0; i < h; i++) scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].t); sort(a,a+h,cmp); int sign=0; for(int i = 0; i < h; i++){ sign = 0; for(int j = a[i].s; j <= a[i].e; j++){//判断已经存在多少点 if(book[j]) sign++; } if(sign >= a[i].t) continue; for(int j = a[i].e;j >= a[i].s; j--){//画点 if(!book[j]) { book[j] = 1; sign++; num++; if(sign == a[i].t) break; } } } printf("%d ",num); return 0; }另外三个经典应用，后期会抽时间更新。
往者可鉴,来者可追,学习永远不晚!