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();
}
}
}
分享到:
相关推荐
输入n[1, 100]组田忌和齐威王的马的速度,使用贪心法求田忌胜出的最多盘数(赢局数—输局数,平局数不算分),设计贪心策略,实现程序。 输入:组数n[1, 100],田忌和齐威王每组马的速度,每一组包含两个正整数,...
16《田忌赛马》课后作业(含答案)-五下语部编版.pdf
田忌与齐王赛马,双方各有n匹马参赛(n),每场比赛赌注为1两黄金,现已知齐王与田忌的每匹马的速度,并且齐王肯定是按马的速度从快到慢出场,现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金(输用负数...
田忌赛马问题田忌赛马问题田忌赛马问题田忌赛马问题田忌赛马问题
齐王和田忌均有n(1到100的整数)匹马 只有当田忌马的战力值大于齐威王马的战力值时 田忌才能赢 问田忌最多能赢几场 其中战力值用整数表示
《田忌赛马》课件(第二课时).ppt
如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。 请问田忌最多能赢多少...
mathematica软件解决实际问题——田忌赛马3.pdf
高级人工智能博弈田忌赛马解题
数学广角——田忌赛马演示PPT课件.pptx
分别输入田忌和齐王的马的速度。先排好序,再分情况讨论,代码易懂,仔细看看。不懂就调试一下。
本人亲身经历的华为机试题,希望对即将参加华为校招的同学有一定的帮助。
数学四上田忌赛马PPT课件.pptx
之前帮别人写的田忌赛马博弈矩阵分析,java实现,有需要的可以参考欢迎提出意见
算法实验,采用动态规划的思想,已通过测试。
16《田忌赛马》说课稿.pdf
16《田忌赛马》说课稿(统编版小学语文五年级下册精品).pdf
最新人教版四年级数学上册《田忌赛马问题》课时练习--.pdf