贪心算法部分题目总结:

一:背包问题
背包问题与最优装载问题十分类似,都是取优先级别级别最高或较高的变量进行处理,其中分为两种类型:变量(货物)可拆分/不可拆分两类;对于这两类类型,可以先将其性价比一一算出,先装性价比较高的,然后依次降低,直到背包装满货物,需要注意的一点就是比较,在快装满时比较出是否背包可全部装进该物品,若不可则进行分割或装入下一个能装进且性价比较高的物品(不可分割时)。(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 没有这个功能,算法不能保证这一点。