《挑战程序设计竞赛》学习笔记 （1）

2.2 贪心法

• 贪心法是遵循某种规则，不断贪心选取当前最优策略的算法设计方法。
  • 贪心法的求解思想是通过迭代地选取当前问题的局部最优解法来达成总体最优解，在迭代的过程中不断地产生局部最优解和下一个与之前问题同构的子问题。
  • 贪心法所处理的问题总是具有最优子结构的性质：该问题的最优解包含子问题的最优解。
  • 使用贪心法处理的时候如何选取贪心策略非常关键，选定正确的策略往往要求一定的洞察力，验证贪心策略的正确性可能使用数学归纳法或者反证法。
  • 与搜索和动规不同，贪心法的特点是解决问题的顺序是固定的，而且不能回退。证明贪心策略在整体逻辑上一部分是为了证明贪心策略所确定的解题顺序是否可以保证得到整体最优解，但是在具体的问题中这种目的可能不是那么明显。
• 例题
  • 硬币问题——入门：与搜索和动态规划不同，贪心法遵循某种规则，不断选取当前最优策略。注意结合题目中硬币面额他考虑贪心策略
  • 区间调度问题——开始涉及贪心策略的差异，尝试证明，☀专栏
  • 字典序最小问题（POJ3617）——理清思路，了解解题的一般方法
  • 其他问题之 Saruman's Army：较易
  • 其他问题之☀Fence Repair：了解自顶向下/自底向上的解决思路，强化解题的一般方法（此题自己想了一下，思路还算清楚，可以记录下来供以后参考）
• 练习题（page135）
  • 区间
    • POJ 2376：Clean Shifts（AC）
      

       1 #include <iostream>
       2 #include <stdio.h>
       3 #include <algorithm>
       4 #include <vector>
       5 using namespace std;
       6 
       7 const int maxn = 25005;
       8 
       9 struct COW
      10 {
      11     int begin,end;
      12 };
      13 
      14 bool cmp(COW a, COW b)
      15 {
      16     if(a.begin==b.begin)
      17         return a.end<b.end;
      18     return a.begin<b.begin;
      19 } 
      20 
      21 int main()
      22 {    
      23     //freopen("F:\课程文件夹\课程之外\ACM文件库\挑战程序设计\数据\test data.txt","r",stdin);
      24 
      25     //输入
      26     int N,T;
      27     scanf("%d%d",&N,&T);
      28     COW cows[maxn];
      29     for(int i=1;i<=N;i++)
      30         scanf("%d %d",&cows[i].begin,&cows[i].end);
      31      
      32     //排序 
      33     sort(cows+1, cows+N+1, cmp);
      34     
      35     //SOLVE
      36     int S=0,temp=1,max=0,ans=0;
      37     while(S<T)
      38     {
      39         
      40         for( ; cows[temp].begin<=S+1 && temp<=N; temp++ )
      41         //在起始时间早于已填充时间的cow里寻找最晚结束工作的cow 
      42             max=cows[temp].end>max?cows[temp].end:max;
      43 
      44         if(S==max)
      45         //在已填充时间内找不到可接替并在更晚时间工作的牛，之后死循环 
      46             break;
      47         S=max;        
      48         ans++;
      49     }
      50     
      51     if(S<T)
      52         ans=0;
      53 
      54     ans>0? cout<<ans<<endl : cout<<-1<<endl;
      55 } 

      View Code