当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

田忌赛马: POJ 2287(贪心解法)

发表于: 2013-01-03   作者:128kj   来源:转载   浏览:
摘要: POJ 2287问题描述: 你一定听过田忌赛马的故事吧?     如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。 请问田忌最多能赢多少银子? 关于输入:   输入包含多组测试数据,每组测试数据的第一行是一个整
POJ 2287问题描述:
你一定听过田忌赛马的故事吧?
    如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。 请问田忌最多能赢多少银子?

关于输入:
  输入包含多组测试数据,每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数,表示田忌的马的速度,下一行也是n个整数,表示齐王的马的速度。 输入的最后以一个0表示结束。

关于输出:

   对每组数据,输出一个整数,表示田忌至多可以赢多少银子,如果田忌赢不了,就输出一个负数,表示田忌最少要输多少银子。

例子输入:

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0

例子输出:
200
0
0

解题思路:
   贪心算法。如果当前最好的马可以胜齐王最好的马,那么让这两匹马比一场。如果当前最差的马能胜齐王最差的马,那么让这两匹马比一场。如果上面两个条件都不满足,那么让当前最差的马和齐王最好的马比一场。

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
 public class Main{
    public static void main(String args[]){  
        int n, m;  
        List<Integer>  vTian=new ArrayList<Integer>();
        List<Integer>  vQi=new ArrayList<Integer>();
        Scanner in=new Scanner(System.in);

      
        while(true){  
          n=in.nextInt();
          if(n==0) break;

            //输入数据  
            for(int i = 0; i < n; ++i)  
            {  
                vTian.add(in.nextInt());  
            }  
            for(int i = 0; i < n; ++i)  
            {  
                 vQi.add(in.nextInt());  
            }  
            //处理数据  
            Collections.sort(vTian);  
            Collections.sort(vQi);  
      
            int i=0, j=0, x=n-1, y=n-1,cnt=0;  
            boolean bLast=true;  
      
            while(bLast)      
            {  
                //是否是最后一匹马  
                if(x==i)  
                    bLast=false;  
                  
                if(vTian.get(x) > vQi.get(y))  
                {//如果田忌当前最好的马可以胜齐王最好的马,那么比一场  
                    x--;  
                    y--;  
                    cnt+=200;  
                }  
                else if(vTian.get(i)> vQi.get(j))  
                {//如果田忌当前最差的马可以胜齐王最差的马,那么比一场  
                    i++;  
                    j++;  
                    cnt += 200;  
                }  
                else  
                {//否则,让田忌最差的马和齐王最好的好比一场  
                    if(vTian.get(i) < vQi.get(y))  
                        cnt -= 200;  
                    i++;  
                    y--;  
                }  
            }  
           System.out.println(cnt);
            vTian.clear();  
            vQi.clear();  
        }  
      
       }
    }  


田忌赛马: POJ 2287(贪心解法)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
 Tian Ji -- The Horse Racing Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 1249
Tian Ji -- The Horse RacingTime Limit: 5000MS Memory Limit: 65536K Total Submissions: 7104 Ac
Tian Ji -- The Horse Racing Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 9328 A
Moving Tables Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others
虽然A掉了但是时间感人啊.... f( x, k ) 表示使用前 x 种填满容量为 k 的背包的方案数, g( x , k )
这两天碰到一道看似很简单,但是实际做起来确实比较难的问题,在这里分析讨论一下。 题目:http://a
分析:题意 源岸数量<=3 很好判断 3:num[0]+num[1]+num[2] 2:num[1] ,1:num[0] 源岸数量>3 #i
Pass-Muraille Time Limit: 2 Seconds Memory Limit: 65536 KB In modern day magic shows, passing
Radar Installation Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 64148 Accepted:
题意:已知有400个房间,有n张桌子必须从a 房间搬到 b 房间,搬每张桌子所花的时间都是10分钟。走廊
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号