典型的贪心算法~ (田忌赛马 )

2014年7月31日 3点热度 0条评论 来源: OnlyTyou

     1. 田忌赛马

 典型的贪心算法~~自己木有考虑到贪心的第二步导致wa了好多次

算法分析 

Problem Description:

给出2N组数据,分别表示田忌和齐威王的N匹马的速度,没进行一场比赛(每组数据共N场场赛),若能分出胜负,则输的一方要给赢的一方200Y¥(银元),求田忌以怎样的策略才能赚取最多的老婆本。

Solution:这题有多种解体思路,DP,二分图最大匹配算法等,这里给出的是比较容易理解的贪心算法,具体思路如下:

先将田忌跟齐王的马的速度数组进行一次冒泡排序

1、如果田忌最快的马比齐王最快的马快,则比之

2、如果田忌最快的马比齐王最快的马慢,则用田最慢的马跟齐最快的马比  //这是贪心的第一步

3、如果田忌最快的马的速度与齐威王最快的马速度相等

3.1、如果田忌最慢的比齐威王最慢的快,则比之                         //这是贪心的第二步

3.2、如果田忌最慢的比齐威王最慢的慢,田忌慢VS齐王快

3.3、田忌最慢的与齐威王最慢的相等,田忌慢VS齐王快

注意这两种 数据

3

1 2 3

92 83 71 tian 第一步 tian1对king1 转到2 贪心的第一次,

95 92 74 king 第二步tian1对king2 转到3.1 (贪心的第二次 保留tian的快马 )

第三步 只剩下一种选择了~~3 92 83 70 92 91 60

*********代码

#include<stdio.h>   
#include<iostream>   
#include<algorithm>   
using namespace std;  
int a[3000],b[3000];  
int cmp(int a,int b)  
{  
  return a>b;      
}  
int main()  
{  
   int i,n,j,sum,k,f,ji;  
   while( scanf("%d",&n) && n!=0 )  
   {  
      for(i=0;i<n;i++)  
        scanf("%d",&a[i]);    
      for(i=0;i<n;i++)        
        scanf("%d",&b[i]);  
      sort(a,a+n,cmp);     
      sort(b,b+n,cmp);  
      ji=0;    //   记录 king  比赛用的马  循环跳出的判定条件    
      i=j=sum=0;  
      k=n-1;  
      f=n-1;  
      while(1)  
      {             
          if(ji==n)   break;   //   king  的马全部比完后跳出    
          if(b[j]>a[i]) {   sum-=200;j++;k--;ji++; continue;}  //如果king的比tian的快马快 用tian的慢马对king的快马    
          if(b[j]==a[i]){                                       //如果相等    
                            if(b[f]<a[k]){f--;k--;sum+=200;ji++;continue;} //看两人的慢马 tian的慢马比king的慢马快则比    
                            if(b[j]>a[k]){sum-=200;k--;j++;ji++;}  
                            else {k--;j++;ji++;}  
                            continue;  
                        }  
          if(b[j]<a[i]){sum+=200;j++;i++;ji++;continue;}  //如果tian的比king的快马快 直接比    
      }            
      printf("%d\n",sum);      
   }  
}  

           

            

    原文作者:OnlyTyou
    原文地址: https://blog.csdn.net/u013514722/article/details/38317509
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。