多写题解多交流才能学好 oi。
在这里贴了代码，为了看上去完整一些。
大概是一些自己学习的记录罢。
贪心不算客观意义上的算法，感觉还不算一种策略机制。我认为更像一种思路，其内涵就是择优，解题时就去想怎样才能更优。
根据最优的思路能去做很多，如果说贪心是一个题的正解的话太抽象，因此贪心的重点也是在证明。
一般证明可以用反证法。
有时不能验证正确性，也可以适当骗分。
感觉贪心蛮好玩的，挺考察思维能力。
经典题：
1.syoj.1501 最多不相交线段。P1803 凌乱的yyy / 线段覆盖
这个就是找到最多的不相交线段条数。答案是考虑按照右端点从小到大排序，最大限度的向左边缩，不要往右边伸展，然后用这个选定的线段将不符合条件的线段筛掉。即一个点既然能被一条线段覆盖，那就让这条线段尽量的短。
但在 syoj 上会卡奇奇怪怪的东西，输入的时候注意判断一下 l 和 r，右边的不一定比左边大。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int n, ans;
int vis[N];
struct node{int a, b;} k[N];
bool cmp(node x, node y)
{
return x.b < y.b;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++ )
{
scanf("%d%d", &k[i].a, &k[i].b);
if(k[i].b < k[i].a) swap(k[i].a, k[i].b);
}
sort(k + 1, k + n + 1, cmp);
for(int i = 1; i <= n; i ++ )
{
if(!vis[i])
{
ans ++;
vis[i] = 1;
for(int j = i + 1; j <= n; j ++ )
{
if(k[i].b > k[j].a) vis[j] = 1;
}
}
}
printf("%d", ans);
return 0;
}
2. syoj.1502 区间最少覆盖线段 AcWing 907.区间覆盖
思路和上面那个一模一样吧。按左端点从大到小排序，尽可能的向右延伸。每个点，若有两条线段覆盖，一定找右端点更靠右的那条。
#include<iostream
#include<algorithm>
using namespace std;
const int N=100010;
int n;
struct Range{
int l,r;
bool operator< (const Range &W)const{
return l<W.l;//按左端点排序
}
}range[N];
int main(){
int st,ed;
scanf("%d%d",&st,&ed);//start end
scanf("%d",&n);
for(int i=0;i<n;i++){
int l,r;
scanf("%d%d",&l,&r);
range[i]={l,r};
}
sort(range,range+n);
int res=0,success=0;
for(int i=0;i<n;i++){
int j=i,r=-2e9;
while(j<n&&range[j].l<=st){//只要这个区间可以覆盖
r=max(r,range[j].r);//右边的端点最能靠右
j++;//一直往后找区间
}
if(r<st){//结果找了一遍都不能覆盖到
res=-1;//那就说明无解
break;
}
res++;
if(r>=ed){//说明找到咧
success=1;
break;
}
st=r;
i=j-1;//这之前的都不行就不看了
}
if(!success) res=-1;
printf("%d",res);
}
3.洛谷 P1106 删数问题 传送门
很有趣的有趣题，一开始都容易想假每次删最大的。反例很好找。
在几次尝试后就能发现，每次最优应该删掉该数字的第一个“峰值”。这样找到的数字靠前，影响力大。而对于答案的贡献，因为是一个“峰”，所以其后数字一定比其小，所以删掉后一定最优。
特别注意前导 0。
#include<bits/stdc++.h>
using namespace std;
const int N = 255;
char s[N];
int len, k;
int main()
{
cin >> s >> k;
len = strlen(s);
while(k -- )
{
for(int i = 0; i < len; i ++ )
{
if(s[i] > s[i + 1])
{
for(int j = i; j < len; j ++ ) s[j] = s[j + 1];
break;
}
}
len --;
}
int i = 0;
while(s[i] == '0' && i < len) i ++;
if(i == len) cout << "0";
else for(; i < len; i ++ ) cout << s[i];
}
其他好玩的题还没写捏。