所以我现在弱到贪心都不会做了？啊这。。。。。。
贪心，是一种只考虑局部最优，而不顾全局最优的算法。
这类算法通常思维性比较强，代码量比较短，适合拿来考思维。
基本上的贪心题目都要排序。
而且贪心经常容易和 dp 混淆（当然有了一定水平之后就不会混淆了）。
贪心的题目类型有很多，但是不管哪种类型的题目平常做之前我们都要严谨证明一遍贪心法的正确性。当然考场上用就行了，实在不会证不管他。
题单：
A - Cleaning Shifts[OpenJ_Bailian - 2376]
题目大意：给你 \(n\) 段区间，从中取出最少的区间使得这些区间能完全覆盖 \([1,t]\)，求个数。\(1 \leq n \leq 25000,1 \leq t \leq 1000000\)。
解法：区间覆盖问题。
按照左端点升序排序，先把第一个区间取来，然后求 \(\max_{i \in [1,n] \& l_i \leq r_i}{r_i}\)，更新右端点然后重复执行上述操作，重复时之前统计过的区间不再统计。
代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25000 + 10;
int n, t;
struct node
{
int l, r;
}a[MAXN];
int read()
{
int sum = 0, fh = 1; char ch = getchar();
while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) fh = -1; ch = getchar();}
while (ch >= ‘0‘ && ch <= ‘9‘) {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
return sum * fh;
}
bool cmp(node fir, node sec) {return fir.l < sec.l;}
int main()
{
n = read(); t = read();
for (int i = 1; i <= n; ++i) {a[i].l = read(); a[i].r = read();}
sort(a + 1, a + n + 1, cmp);
int j = 1, p = 0, ans = 0;
for (int i = 1; i <= n; i = j)
{
int r = 0;
while (j <= n && a[j].l <= p + 1) r = max(r, a[j++].r);
if (!r) break;
p = r;
ans++;
if (r >= t) break;
}
if (p < t) printf("-1\n");
else printf("%d\n", ans);
return 0;
}
题目大意：给你 \(n\) 个区间，保证在 \([1,n]\) 范围内，从中选出尽量多的无交集区间。\(1 \leq n \leq 100\)。
解法：最多区间问题。
按照右端点排序，然后一个一个选过去即可，每次记录最右边的点，有交集不选，无交集就选。
代码：
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
using namespace std;
const int MAXN = 100 + 10;
int n, ans;
struct node
{
int l, r;
}a[MAXN];
int read()
{
int sum = 0, fh = 1; char ch = getchar();
while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) fh = -1; ch = getchar();}
while (ch >= ‘0‘ && ch <= ‘9‘) {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
return sum * fh;
}
bool cmp(const node &fir, const node &sec)
{
if (fir.r ^ sec.r) return fir.r < sec.r;
return fir.l < sec.l;
}
int main()
{
while ((n = read()) != 0)
{
for (int i = 1; i <= n; ++i) {a[i].l = read(); a[i].r = read();}
sort(a + 1 ,a + n + 1, cmp);
int las = a[1].r, ans = 1;
for (int i = 2; i <= n; ++i)
{
if (a[i].l >= las)
{
las = a[i].r;
ans++;
}
}
printf("%d\n", ans);
}
return 0;
}
C - Radar Installation[POJ - 1328]
咕咕咕~
咕咕咕~
咕咕咕~
F - Tian Ji -- The Horse Racing[HDU - 1052]
咕咕咕~
咕咕咕~
原文：https://www.cnblogs.com/zhuzehao/p/14185995.html