贪心搞了5天的时间。。。。略坑。贪心呢，其实就是一种思想，在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。其实贪心用的最多的东西就是快排，我感觉做的每题都用到了快排，有的也用到了结构体。

　　1.HDOJ 1009 FatMouse' Trade

　　　　这一题是说catfood与javabean之间可以互换，然后找最多可以换多少个javabean。这就与交换率有关了，优先满足交换率高的，肯定得到的javabean就多 了。用结构体记录，然后快排即可。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 struct node{ 8     int k; 9     int i;10     double bili;11 }cat[1001];12 int cmp(node a,node b){13     return  a.bili>b.bili;14 }15 int main(){16     int n,m;17     while(scanf("%d%d",&m,&n)&&(m!=(-1))){18         int f,j;19         for(int i=0;i
           
            =(double)cat[i].i){31 temp-=(double)cat[i].i;32 ans+=(double)cat[i].k;33 //printf("%.3lf\n",temp);34 }35 else{36 ans+=temp*cat[i].bili;37 //printf("%.3lf\n",temp);38 break;39 }40 }41 printf("%.3lf\n",ans);42 }43 return 0;44 }
           
          
         
        
       
      

　　2.HDOJ 1050 

　　　　这题的基本解法：初始化数组，如果需要移动，自增一，代表一个操作，最后便历，找出操作数做多的那个，就是我们需要的最长时间。

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 int p[205]; 5 int main() 6 { 7     int T , n , s ,d , t,min  , temp; 8     cin >> T; 9     while(T--)10     {11 12             for(int j = 0; j < 200 ; j++)13             {14                 p[j] = 0;15             }16             cin >> t;17             for(int j= 0 ; j < t ; j++)18             {19                 cin >> s >> d;20                 s = (s - 1) / 2;//奇偶对门21                 d = (d - 1) / 2;22                 if(s > d)23                 {24                     temp = s;25                     s = d ;26                     d = temp;27                 }28                 for(int k = s ; k <= d; k++)29                 {30                     p[k] ++;31                 }32 33             }34             int max = -1;35             for(int j = 0 ; j < 200 ; j++)//找出用得最多的那个36             {37                 if(p[j] > max)max = p[j];38             }39             cout << max *  10 <
       
      

　　3.HDOJ 2037 

　　　　这个题就是一个安排时间表的题，有很多电视节目，然后告诉你开始时间和结束时间，问你最多能安排多少个节目。我们可以先对电视节目结束的时间进行排序，然后，向前找不冲突最多的电视节目个数就行。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 struct jiemu{ 8     int start; 9     int end;10     int length;11 }ti[101];12 int cmp(jiemu a,jiemu b){13     return a.end
           
            =temp){29 ans++;30 temp=ti[i].end;31 }32 }33 printf("%d\n",ans);34 }35 return 0;36 }
           
          
         
        
       
      

　　4.HDOJ 1051  Wooden Sticks

　　　　题目意思是让你求操作的时间，开机需要1分钟，然后如果后一个的长度或质量比前一个小的话需要调整，需要1分钟，求安排的最少时间。我们排序的时候就可以依据那个要求排序，先按长度的由小到大排序，如果长度相等就按质量由小到大排序。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7  8 struct sticks{ 9     int length;10     int weigth;11     int flag;12 }arr[5001];13 14 int cmp(sticks a,sticks b){15     if(a.length!=b.length)  return a.length
           
            =temp){37 temp=arr[j].weigth;38 arr[j].flag=1;39 }40 }41 ans++;42 }43 }44 printf("%d\n",ans);45 }46 return 0;47 }
           
          
         
        
       
      

　　5.HDOJ 2545 

　　　　一句话，顶点的度序列 Havel 定理~

　　　　定义：给出一个无向图的顶点度序列 {dn}，要求判断能否构造出一个简单无向图。

　　　　分析：

    　　　　贪心的方法是每次把顶点按度大小从大到小排序，取出度最大的点Vi，依次和度较大的那些顶点Vj连接，同时减去Vj的度。连接完之后就不再考虑Vi了，剩下的点再次排序然后找度最大的去连接……这样就可以构造出一个可行解。

判断无解有两个地方，若某次选出的Vi的度比剩下的顶点还多，则无解；若某次Vj的度减成了负数，则无解。

　　　　　　　

　　　　　　至于什么是Havel定理，上面这个构造过程就是了~（转自别人的博客。。。。）。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int d[1002]; 7 bool gr(int a,int b) 8 { 9     return a>b;10 }11 int main()12 {13     int t,n;14     scanf("%d",&t);15     while(t--){16         scanf("%d",&n);17         memset(d,0,sizeof(d));18         for(int i=0;i
         
        
       
      

　　6.HDOJ 1052 Tian Ji -- The Horse Racing

　　　　田忌赛马，求他的最优解。其实我觉得这题像模拟，因为题目已经把怎么选马告诉你了。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 int arr1[1001],arr2[1001]; 8 int cmp ( const void *a , const void *b ) 9 {10     return *(int *)a - *(int *)b;11 }12 int main(){13     int n;14     while(scanf("%d",&n)&&n!=0){15         for(int i=0;i
           
            arr2[begin2]){24 begin1++;25 begin2++;26 ans++;27 continue;28 }29 if(arr1[end1]>arr2[end2]){30 end1--;31 end2--;32 ans++;33 continue;34 }35 if(arr1[begin1]