贪心算法部分题目总结：
一：背包问题
背包问题与最优装载问题十分类似，都是取优先级别级别最高或较高的变量进行处理，其中分为两种类型：变量(货物）可拆分/不可拆分两类；对于这两类类型，可以先将其性价比一一算出，先装性价比较高的，然后依次降低，直到背包装满货物，需要注意的一点就是比较，在快装满时比较出是否背包可全部装进该物品，若不可则进行分割或装入下一个能装进且性价比较高的物品（不可分割时）。（FATMOUSE’ TRADE看守仓库问题与之类似，也是寻找最优性价比问题）
二：删数问题
n位数中删去k位数，使得剩下的数字组成的整数最小。
可以采取x[i+1]与x[i]比较，如果x[i+1]比较小的话，则删去x[i]；
当删去1位数字以后。原问题变成了对n-1位删去k-1位，有点像递归。
三：多处最优服务次序问题
设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti，1≤i≤n，共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。
对服务时间最短的顾客先服务的贪心选择策略。（使用贪心算法时）
这道题类似于之前的接水问题，上次已经写到。
四：moving tables
在经理给出的说明表格中，已经明确地描述了算法：
（从房间30到50）和（从房间60到90）是允许的，因为没有占用公共的走廊；
（从房间20到40）和（从房间31到80）是不允许的，因为要占用公共的走廊。
我们将每个房间之间的走廊作为一个统计单位，当所有的办公桌都搬运完成之后，看看这段走廊到底需要占用多少次？然后统计所有的走廊被占用的最大值max，这个值就是要单独安排的搬运次数，乘以10就是总的搬运时间。
int i, j;
int move[200];
int N; //搬运次数
//每次搬运的起点和终点
int from, to;
scanf("%d", &N);
memset(move, 0, sizeof(move));
for(i = 0; i < N; i++)
{
scanf("%d%d", &from, &to);
//将房间号映射为走廊号
from = (from - 1)/2;
to = (to - 1)/2;
//确保from<to，C++使用：swap(from, to)
if(from > to) {
int temp = from;
from = to;
to = temp;
}
//占用走廊情况
for(j = from; j <= to; j++)
move[j]++;
}
//所有的走廊被占用的最大值
int max = 0;
for(i = 0; i < 200; i++)
if(move[i] > max) max = move[i];
printf("%d\n", max * 10);
五：均分纸牌
有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ① 9 ② 8 ③ 17 ④ 6
移动3次可达到目的：
从 ③ 取4张牌放到④（9 8 13 10）->从③取3张牌放到 ②（9 11 10 10）-> 从②取1张牌放到①（10 10 10 10）。
【输入格式】
N（N 堆纸牌，1 <= N <= 100）
A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
【输出格式】
所有堆均达到相等时的最少移动次数。
【样例输入】Playcard.in
4
9 8 17 6
【样例输出】Playcard.out
3
这个题目要求我们考虑平均数问题，因为最终状态我们要得到每堆牌数都相等，在这个基础上我们可以简化一下问题，使该平均数为零，刚开始未移动的纸牌从这个基础上进行赋值变化，这时我们的目标就是使每堆纸牌数都变成零。
cin>>n;
ave=0;step=0;
for (i=1;i<=n;++i)
{
cin>>a[i]; ave+=a[i]; //读入各堆牌张数，求总张数ave
}
ave/=n; //求牌的平均张数ave
for (i=1;i<=n;++i) a[i]-=ave; //每堆牌的张数减去平均数
i=1;j=n;
while (a[i]==0&&i<n) ++i; //过滤左边的0
while (a[j]==0&&j>1) --j; //过滤右边的0
while (i<j)
{
a[i+1]+=a[i]; //将第i堆牌移到第i+1堆中去
a[i]=0; //第i堆牌移走后变为0
++step; //移牌步数计数
++i; //对下一堆牌进行循环操作
while (a[i]==0&&i<j) ++i; //过滤移牌过程中产生的0
}
cout<<step<<endl;
六：整数区间
请编程完成以下任务：
1.读取闭区间的个数及它们的描述；
2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。
【输入】
首行包括区间的数目n,1<=n<=10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0<=a<=b<=10000,它们是某一个区间的开始值和结束值。
【输出】
第一行集合元素的个数,对于每一个区间都至少有一个整数属于该区间,且集合所包含元素数目最少。
【样例输入】
4
3 6
2 4
0 2
4 7
【样例输出】
2
我们先可以找到重复的元素，然后利用这个元素去一一排除多余的集合，当然我们可以通过排序来在最小集合的右端（最大值）进行一一查找，具体类似于下图：
•算法模型：给n个闭区间[ai,bi], 在数轴上选尽量少的点,使每个区间内至少有一个点。
•算法：首先按b1<=b2<=…<=bn排序。每次标记当前区间的右端点x，并右移当前区间指针，直到当前区间不包含x,再重复上述操作。
•如下图，如果选灰色点，移动到黑色点更优。
#include<iostream>
using namespace std;
int a[10001],b[10001],sum=0,n,m;
void qsort(int x,int y) //多关键字快排
{
int i,j,mid1,mid2,t;
i=x;j=y;mid1=b[(x+y)/2];mid2=a[(x+y)/2];
while(i<=j)
{ while(b[i]<mid1||((b[i]==mid1)&&(a[i]<mid2))) ++i;
while(b[j]>mid1||((b[j]==mid1)&&(a[j]>mid2))) --j;
if(i<=j)
{ t=b[j];b[j]=b[i];b[i]=t;
t=a[j];a[j]=a[i];a[i]=t;
++i; --j;
}
}
if(x<j) qsort(x,j);
if(i<y) qsort(i,y);
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i]>>b[i];
qsort(1,n);
for(int i=1,x=-1;i<=n;++i) //在初始化循环变量的同时，初始化x。
//令x=-1可以使第一个区间与其他区间的操作
相同。
{
if (x>=a[i]) continue; //如果当前区间包含标记点，就跳过。
++sum; x=b[i]; //更新标记点。
}
cout<<sum<<endl;
return 0;
}
stable_sort 和 sort的区别:
stable_sort 和 sort的区别在于前者作排序可以使原来的"相同"的值在序列中的相对位置不变。这是稳定排序函数，当重量相同时，保持输入数据原来的顺序。
如 1 4 6 7 4’ (4 和 4’值相等,加上’ 表示是2个元素)
那么stable_sort能保证排序完 4 仍然在4’前也就是输出1 4 4’ 6 7;但是sort 没有这个功能,算法不能保证这一点。
京公网安备 11010502036488号