`
128kj
  • 浏览: 600104 次
  • 来自: ...
社区版块
存档分类
最新评论

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

阅读更多
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();  
        }  
      
       }
    }  


分享到:
评论

相关推荐

    田忌赛马.zip_田忌赛马_田忌赛马 贪心_田忌赛马问题

    输入n[1, 100]组田忌和齐威王的马的速度,使用贪心法求田忌胜出的最多盘数(赢局数—输局数,平局数不算分),设计贪心策略,实现程序。 输入:组数n[1, 100],田忌和齐威王每组马的速度,每一组包含两个正整数,...

    数学广角——田忌赛马演示PPT课件.pptx

    数学广角——田忌赛马演示PPT课件 本PPT课件主要介绍了数学中的策略思想,通过田忌赛马的故事,讲解了数学中策略的重要性和应用。 第一页:故事的开始,讲述田忌赛马的故事,并引入数学的角度来理解田忌的策略。 ...

    田忌赛马问题 C语言

    田忌与齐王赛马,双方各有n匹马参赛(n),每场比赛赌注为1两黄金,现已知齐王与田忌的每匹马的速度,并且齐王肯定是按马的速度从快到慢出场,现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金(输用负数...

    16《田忌赛马》课后作业(含答案)-五下语部编版.pdf

    《田忌赛马》是中国古代著名的历史故事,讲述了春秋时期齐国贵族田忌和齐威王赛马,通过智者孙膑的计策,以弱胜强的故事。本课后作业围绕这一故事,不仅要求学生复习故事内容,还要求他们进行词义理解、句子填空、...

    田忌赛马源代码

    齐王和田忌均有n(1到100的整数)匹马 只有当田忌马的战力值大于齐威王马的战力值时 田忌才能赢 问田忌最多能赢几场 其中战力值用整数表示

    田忌赛马C语言实现

    分别输入田忌和齐王的马的速度。先排好序,再分情况讨论,代码易懂,仔细看看。不懂就调试一下。

    田忌赛马问题c语言代码

    田忌赛马问题田忌赛马问题田忌赛马问题田忌赛马问题田忌赛马问题

    mathematica软件解决实际问题——田忌赛马3.pdf

    "mathematica软件解决实际问题——田忌赛马3" 本文将通过Mathematica软件解决田忌赛马问题,使用编程语言来模拟和解决实际问题。 问题描述 田忌赛马是一则古代中国的典故,说的是战国时代的齐王与其大将田忌赛马...

    c语言版田忌赛马

    如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。 请问田忌最多能赢多少...

    《田忌赛马》课件(第二课时).ppt

    《田忌赛马》课件(第二课时).ppt知识点总结 本节课的主要目标是通过对话和故事的学习,掌握人物性格特点的分析方法和表达方法,并能有感情地朗读对话,复述课文,讲述有关智慧的故事。 一、学习目标 1. 抓住...

    16《田忌赛马》说课稿(统编版小学语文五年级下册精品).pdf

    但是,从标题和描述可以推断出,这是一份关于小学语文五年级下册中《田忌赛马》一文的说课稿。而标签部分为空,无法提供额外信息。 从内容部分提供的数字和句式来看,这似乎是OCR扫描结果中的一部分,其中包含了...

    16《田忌赛马》说课稿.pdf

    文档标题《田忌赛马》说课稿暗示了这是一份教育领域关于古代故事《田忌赛马》的讲解材料,可能用于教师准备课堂内容或学生准备演讲。但没有提供具体的内容供我分析和生成知识点。如果您能提供文件的正文内容,我将...

    田忌赛马博弈矩阵分析

    之前帮别人写的田忌赛马博弈矩阵分析,java实现,有需要的可以参考欢迎提出意见

    田忌赛马与孙膑智谋PPT模板.pptx

    "田忌赛马与孙膑智谋PPT模板.pptx" 本PPT模板主要讲述了田忌赛马和孙膑智谋两个故事,并对其历史影响、文化内涵、现代启示和艺术创作进行了详细的分析和解读。 一、孙膑智谋 孙膑是中国战国时期的著名军事家,他...

    华为机考 中级题 田忌赛马

    对即将参加华为机考的同学有极大的帮助,完美解决了田忌与国王赛马,田忌最对能够赢得的赛马场数。

    田忌赛马FLASH课件

    这是个FLASH课件,希望对大家有帮助,虽然只是个初学者,但希望交到更多的朋友!

    四年级数学上册田忌赛马课件PPT学习教案.pptx

    1. **策略优化**:田忌赛马的故事展示了如何通过策略优化来赢得比赛,即使在资源有限的情况下。在这个案例中,田忌利用了他的马的优势和劣势,通过调整出场顺序,使得他在至少两个场次中胜出,从而赢得了整体比赛。...

    数学四上田忌赛马PPT课件.pptx

    数学四上田忌赛马PPT课件.pptx

Global site tag (gtag.js) - Google Analytics