注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj hdu Tian Ji -- The Horse Racing 贪心  

2011-04-21 18:59:50|  分类: 贪心 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
田忌赛马
先把田忌和国王的马排序。
每次取田忌的最快的马与国王最快的马比较,有三种情况。
一,田忌最快的马比国王最快的快,那么直接拿田忌最快的马去赢国王最快的马。
二,田忌最快的马比国王最快的慢,那么拿田忌最慢的马去输国王最快的马。
三,田忌最快的马与国王最快的马速度一样。这时就比较麻烦一点了。
      先拿田忌最慢的马与国王最慢的马比较。
      若比国王快,直接去赢掉国王最慢的马。
      否则田忌最慢的马再去与国王最快的马比较,此时这两只马必定是要比赛的,只是比较一下速度而以。

给一些测试数据:
输入:
2
4 6
3 6
2
4 6
5 6
2
0 3
0 4
2
0 3
0 2
3
6 7 8
6 6 7
3
1 3 3
2 2 3
3
1 3 5
2 2 5
3
7 8 8
6 8 9
3
4 5 5
5 5 5
4
5 6 7 8
2 4 6 7
输出:
200
0
0
200
400
200
200
0
-200
800


#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
       int a[1005],b[1005],n,i,a_H,a_L,b_H,b_L,sum;
       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);
               sort(b,b+n);
               sum=0;
               a_H=0;a_L=n-1;
               b_H=0;b_L=n-1;
               while(b_H<=b_L)
               {
                    if(a[a_L]>b[b_L])
                    {
                         sum+=200;
                         a_L--;b_L--;
                    }
                    else if(a[a_L]<b[b_L])
                    {
                         sum-=200;
                         a_H++;b_L--;
                    }
                    else
                    {
                        while(a_H<=a_L)
                        {
                             if(a[a_H]>b[b_H])
                             {
                                  a_H++;
                                  b_H++;
                                  sum+=200;
                             }
                             else
                             {
                                   if(a[a_H]<b[b_L])
                                   sum-=200;
                                   b_L--;
                                   a_H++;
                                   break;
                             }
                        }
                    }
               }
                                   
               printf("%d\n",sum);  
       }
       return(0);  
}

  评论这张
 
阅读(348)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018