一、最基本问题
常用技巧：排序、维护最优解
例题1：洛谷P1094 纪念品分组
题目大意：
给你n个纪念品，让你发给大家，要求每个人的纪念品数目不能超过2个，并且要使得大家获得的纪念品价值相对比较均衡，每个人的纪念品总价值不能超过m，请问最少能分出多少组。
算法思想：
先给纪念品的价值排个序，排序后前后同时组成纪念品组，这样能保证价值相对均衡。
AC代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 3e4 + 5;
int a[maxn], n, w, ans;
int main(){
cin >> w >> n;
for(int i = 0;i < n;i++)
cin >> a[i];
sort(a, a + n);
int i = 0,j = n - 1;
while(i <= j){
if(a[j] + a[i] <= w){
i++, j--;
ans++;
}else j--, ans++;
}
cout << ans;
return 0;
}
例题2：洛谷P1208 混合牛奶
题目大意：
每位奶农每天只能提供一定量的牛奶，并且他们的单价不同，现在给你一个需求，问你最少花费的多少钱能买到你需要的牛奶量。
算法思想：
他给你的是单价，你就按照单价排序，然后从最便宜开始，依次购买。一旦发现买多了，就退还到上一步操作，对目前可以购买的最小单价去买你还需要的那部分即可。
思考：如果是给你总价呢？你就计算性价比，按照性价比排序即可。
思考：如果对购买的公司家数有限制呢?那这就是一种动态规划的问题了。后面再去补充。
AC代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e6 + 5;
struct Node{
int p, b;
}a[maxn];
int n, m, ans, cnt;
bool cmp(Node n1, Node n2){
return n1.p < n2.p;
}
int main(){
cin >> m >> n;
for(int i = 0;i < n;i++)
cin >> a[i].p >> a[i].b;
sort(a, a + n, cmp);
for(int i = 0;i < n;i++){
cnt += a[i].b;
if(cnt >= m){
cnt -= a[i].b;
ans += (m - cnt)*a[i].p;
break;
}else
ans += a[i].b*a[i].p;
}
cout << ans;
return 0;
}
二、区间调度问题
例题3：洛谷P1803 活动安排问题
题目大意：
给你一个时间表，上面有n个日程计划，每个日程计划对应着它的起止时间。你没有分身术，不能同时去参加两个活动，问你最多能参加多少个活动？
算法分析：
这题显然是一种贪心，但是如何去确定你的贪心策略呢？一个日程，我们可以得到三个关于它的属性：开始时间、结束时间、经历时长。
策略一：如果按照开始时间去排序，也许一个活动，它开始的时间很早，但是它结束的时间很晚，那肯定也不能选取，第一种方案pass！
策略二：
如果按照经历的时长去排序，时间短的活动也许覆盖住了很多时间长的活动，这也是不合理的。
于是我们确定了最终的贪心方案，按照结束时间去排序。
排序完成之后呢？我们可以确定的是，最早结束的活动我们一定是要参加的，因为参加它之后我们再去参加其他活动不会影响最优解。那么如何去确定下一个活动我们是否能够参加呢？只需要比较上一个活动结束的时间和下一个活动开始的时间，如果开始的时间在结束的时间的后面，那么这个活动就可以去参加。然后下一个活动就变成了当前活动，一次类推即可！
AC代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 5;
struct Time{
int a, b;
}t[maxn];
int n, ans, pos;
bool cmp(Time n1, Time n2){
return n1.b <= n2.b;
}
int main(){
cin >> n;
for(int i = 0;i < n;i++)
cin >> t[i].a >> t[i].b;
sort(t, t + n, cmp);
ans = 1, pos = t[0].b;
for(int i = 1;i < n;i++){
if(t[i].a >= pos){
pos = t[i].b;
ans++;
}
}
cout << ans;
return 0;
}
练习题1：HDU 2037 今年暑假不AC
这个题的做法和上面那个例题完全一样，我就不写思路了，AC代码附上：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
int n, pos, ans;
struct Node{
int beg, en;
}a[maxn];
bool cmp(Node n1, Node n2){
return n1.en <= n2.en;
}
int main(){
while(cin >> n && n){
ans = 1;
for(int i = 0;i < n;i++)
cin >> a[i].beg >> a[i].en;
sort(a, a + n, cmp);
pos = a[0].en;
for(int i = 1;i < n;i++){
if(a[i].beg >= pos){
ans++;
pos = a[i].en;
}
}
cout << ans << endl;
}
return 0;
}
练习题2：HDU 1789 Doing Homework again
算法分析：
他有n个作业要写，每个作业具有一下属性：截止时间、扣的分数
最理想的情况就是所有作业都能做完，这样扣的分数最少。但是现实情况可能难以如此理想，所以我们要制定一个优先顺序，哪样的作业要先去做。因为每个作业都有截止日期，所以最着急的肯定就是马上就要去交的作业，所以截止时间最优先；那如果截止时间相同呢？那必然就去做扣分最严重的那一门科目。这个道理是显然的，我们就按此顺序去排序。
排好序之后，我们指定一个时间以天数为单位：k = 1，意思就是从第一天开始去安排做作业的顺序（因为每个作业都要做一天！）
如果到了某一天，有作业交不上了，我们就怀疑是不是之前安排的不妥当，所以去检查前面的安排，查到一个扣分最少的作业，去取代不能完成扣分又较多的那个作业，即可！
AC代码如下：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1005;
int t, n;
struct Class{
int day, score;
int book;//完成状态
}c[maxn];
bool cmp(Class n1, Class n2){
if(n1.day != n2.day)
return n1.day < n2.day;
return n1.score > n2.score;
}
int main(){
cin >> t;
while(t--){
cin >> n;
for(int i = 1;i <= n;i++)
cin >> c[i].day;
for(int i = 1;i <= n;i++){
cin >> c[i].score;
c[i].book = 1;// 先假设都可以完成
}
sort(c + 1, c + n + 1, cmp);
int ans = 0, k = 1;
for(int i = 1;i <= n;i++){
if(c[i].day >= k){
k++;//该作业可以当天完成，安排下一个的作业
continue;
}
int pre = c[i].score, pos = i;// 第i个作业无法当天完成
for(int j = 1;j <= i;j++){
if(pre > c[j].score && c[j].book){
pre = c[j].score;
pos = j;
}
}
ans += pre;
c[pos].book = 0;
}
cout << ans << endl;
memset(c,0,sizeof(c));
}
return 0;
}
拓展练习1：HDU 1050 Moving Table
算法分析：
一个桌子从一个房间移动到另一个房间可以在十分钟内完成，从房间 I 移动到房间 J 的时候，除了[I，J]的部分，其他部分桌子的移动是可以同时进行的。这个题其实很简单啊，就是尽可能地让更多的桌子在相应的移动区间同时移动。然后计算最少用时，所谓最少用时，其实就是最少移动次数乘以10即可。那究竟如何才能知道最少移动次数呢？这里有个坑，大家先看看这幅图：
请仔细观察房间分布
如果我有两个桌子，分别从：1 -> 3，4 -> 5看似这两个移动是不重叠的，实际上重叠了，因为3和4号房间是相对的，他们共用了这段走廊。
而且，移动的方向也不一定是从小房间到大房间，也可能是从大房间到小房间.所以我先需要两步处理：第一、让上下房间位置相对的房间号一致；第二、因为无论是大号房间到小号房间或者是反过来，走过的走廊都是一样的，所以如果是逆序则交换。
存储好了之后，重点来了：我们首先按照路径的起点排序，然后和之前的区间调度方法一样，只是说需要反复使用区间调度，每次都尽可能多的去解决问题，直到所有需要搬桌子的房间都完成了，那么也就完成这次的反复区间调度。
AC代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 205;
int n, t, x, y;
struct Node{
int beg, en;
int book;
}a[maxn];
bool cmp(Node n1, Node n2){
return n1.beg < n2.beg;//一定要按照起点排序
}
int main(){
cin >> t;
while(t--){
cin >> n;
for(int i = 0;i < n;i++){
cin >> x >> y;
if(x % 2) x++;
if(y % 2) y++;// 使得上下房间号位置参考一致
a[i].beg = min(x, y);
a[i].en = max(x, y);
}
sort(a, a + n, cmp);
int flag = 1, cnt = 0, next;
while(flag){
next = -1;
flag = 0;
for(int i = 0;i < n;i++){
if(a[i].beg > next && !a[i].book){
next = a[i].en;
a[i].book = 1;
flag = 1;
}
}
cnt++;
}
--cnt;
cout << cnt*10 << endl;
memset(a,0,sizeof(a));
}
return 0;
}
关于上面这个题，其实还有一种思路，大家可以去试试，大家可以看到，如果走廊上每一个点被走过的次数最大值是x，则区间调度了x次，那么时间就是10*x，这个方法有点类似于前缀和差分。大家可以去试一试，应该是可以做的，我们这里只讨论贪心。
二、区间覆盖问题
算法讲解：
给定了一个长度为n的区间，再给出m条线段的左端点和右端点，问最少使用多少条线段可以将整个区间覆盖？贪心的思路就是尽量找出更长的线段。一般是这样的解题步骤：
一、把每个线段按照左端点升序排序
二、假设已经覆盖的区间是[left，right]，在剩下的线段种找出所有左端点小于等于right且右端点最大的线段，把这个线段加入到已经覆盖了的区间上，更新完成覆盖的区间。然后不断重复这个操作。