田忌赛马,田期思赛马的传说

By admin in 4858.com on 2019年8月24日

田期思赛马,田期思赛马的故事

主题材料陈说

田忌赛马,田期思赛马的传说。本国历史上有个有名的传说:
那是在2300年以前。西夏的大将军田忌喜欢赛马。他平时和齐王赛马。他和齐王都有三匹马:常规马,上级马,超级马。一共赛三局,每局的赢家能够从负者这里获得200银币。每匹马只可以用叁遍。齐王的马好,同等第的马,齐王的接连比田忌的要好一点。于是每趟和齐王赛马,田忌总会输600银币。

田期思很沮丧,直到他相见了盛名的谋士――张仪。田忌采取了苏秦的计策之后,三场交锋下来,轻松而高雅地赢了齐王200银币。那其实是个比相当的粗略的心计。由于齐王总是先出最佳的马,再出次好的,所以田期思用常规马对齐王的超级马,用本身的一级马对齐王的上级马,用本人的上级马对齐王的常规马,以两胜一负的武功获得200银币。实在很简短。

借使持续三匹马如何是好?这么些题目很明显能够转化成七个二分图最好相配的难题。把徐州子期的马放左边,把齐王的马放侧边。田期思的马A和齐王的B之间,若是田期思的马胜,则连一条权为200的边;若是平局,则连一条权为0的边;要是输,则连一条权为-200的边……借使您不会求最好相配,用不大费用最大流也足以啊。
但是,赛马难题是一种奇特的二分图最棒相配的题目,上面的算法过于先进了,大致是杀鸡用牛刀。今后,就请您设计贰个轻巧的算法化解那么些主题素材。

难点陈述

本国历史上有个知名的典故:
那是在2300年在此之前。唐代的里胥田忌喜欢赛马。他时不经常和齐王赛马。他和齐王都有三匹马:常规马,上级马,顶级马。一共赛三局,每局的赢家能够从负者这里获得200银币。每匹马只可以用一回。齐王的马好,同等第的马,齐王的连日比田期思的要好一点。于是每一遍和齐王赛马,田期思总会输600银币。

田期思很懊恼,直到他遇到了享誉的参考――张仪。田期思采取了苏秦的计策之后,三场交锋下来,轻易而雅致地赢了齐王200银币。那实际上是个很轻易的攻略。由于齐王总是先出最棒的马,再出次好的,所以田期思用常规马对齐王的一流马,用自个儿的拔尖马对齐王的上级马,用自身的上级马对齐王的常规马,以两胜一负的武术获得200银币。实在很粗大略。

若果持续三匹马咋做?这几个标题很明朗能够转化成二个二分图最棒相称的难题。把田忌的马放左侧,把齐王的马放侧面。田忌的马A和齐王的B之间,假使田期思的马胜,则连一条权为200的边;假如平局,则连一条权为0的边;假若输,则连一条权为-200的边……假若您不会求最棒相配,用小小开销最大流也足以啊。
然则,赛马问题是一种非常的二分图最棒相配的标题,上面的算法过于先进了,简直是杀鸡用牛刀。以后,就请您安插多少个轻易的算法消除这几个主题素材。

P1650 赛马

主题素材叙述

本国历史上有个著名的有趣的事:
那是在2300年此前。梁国的里正田忌喜欢赛马。他平时和齐王赛马。他和齐王都有三匹马:常规马,上级马,一流马。一共赛三局,每局的赢家能够从负者这里收获200银币。每匹马只可以用一遍。齐王的马好,同等第的马,齐王的连接比田期思的要好一些。于是每回和齐王赛马,田忌总会输600银币。

田期思很消极,直到她超出了令人瞩指标参考――苏秦。田期思选取了苏秦的预谋之后,三场竞赛下来,轻巧而雅致地赢了齐王200银币。那实在是个很轻巧的计划。由于齐王总是先出最棒的马,再出次好的,所以田期思用常规马对齐王的超级马,用本身的一流马对齐王的上级马,用自个儿的上司马对齐王的常规马,以两胜一负的战表获得200银币。实在一点也不细略。

要是持续三匹马怎么办?那一个难题很显然可以转化成四个二分图最好匹配的题材。把田期思的马放左边手,把齐王的马放入手。田期思的马A和齐王的B之间,假使田期思的马胜,则连一条权为200的边;假诺平局,则连一条权为0的边;固然输,则连一条权为-200的边……假诺你不会求最棒相称,用极小费用最大流也能够啊。
但是,赛马难题是一种新鲜的二分图最好相称的难题,上面的算法过于先进了,大致是杀鸡用牛刀。今后,就请你设计贰个简约的算法化解那一个难点。

输入输出格式

输入格式:

第一行一个平头n,表示他们各有几匹马(五个人有所的马的数额一样)。第二行n个整数,各样整数都表示田忌的某匹马的速度值(0
<= 速度值<=
100)。第三行n个整数,描述齐王的马的快慢值。两马相遇,依据速度值的高低就可以领悟哪匹马会胜出。假设速度值一样,则和局,何人也不拿钱。

对于20%的数据,1<=N<=65;

对于40%的数据,1<=N<=250;

对于100%的数据,1<=N<=2000。

出口格式:

仅一行,四个卡尺头,表示田忌最大能博取多少银币。

输入输出格式

输入格式:

 

先是行一个整数n,表示他们各有几匹马(四人所有的马的数量一样)。第二行n个整数,每一个整数都代表田期思的某匹马的快慢值(0
<= 速度值<=
100)。第三行n个整数,描述齐王的马的速度值。两马相遇,依据速度值的大小就可以精晓哪匹皇家赛马会胜出。假若速度值一样,则和局,哪个人也不拿钱。

【数据规模】

对于20%的数据,1<=N<=65;

对于40%的数据,1<=N<=250;

对于100%的数据,1<=N<=2000。

 

出口格式:

 

仅一行,三个卡尺头,表示田期思最大能获得多少银币。

 

标题陈述

本国历史上有个响当当的有趣的事:
那是在2300年以前。南梁的里正田期思喜欢赛马。他平常和齐王赛马。他和齐王都有三匹马:常规马,上级马,一流马。一共赛三局,每局的赢家能够从负者这
里获得200银币。每匹马只可以用一回。齐王的马好,同等第的马,齐王的连接比田期思的要好一些。于是每一趟和齐王赛马,田期思总会输600银币。

田期思很失落,直到她超过了盛名的军师――苏秦。田期思采纳了苏秦的对策之后,三场比赛下来,轻巧而高雅地赢了齐王200银币。那实在是个很简短的计策。由于齐王总是先出最棒的马,再出次好的,所以田忌用常规马对齐王的一级马,用本身的拔尖马对齐王的上级马,用自身的上司马对齐王的常规马,以两胜一负
的战功获得200银币。实在很轻松。

假使持续三匹马如何是好?这一个主题素材很扎眼能够转化成一个二分图最棒相称的标题。把田忌的马放右臂,把齐王的马放出手。田忌的马A和齐王的B之间,如果田忌的马胜,则连一条权为200的边;借使平局,则连一条权为0的边;借使输,则连一条权为-200的边……假设你不会求最棒相配,用小小开支最大流也能够啊。
但是,赛马难点是一种新鲜的二分图最好相称的问题,上边包车型大巴算法过于先进了,简直是杀鸡用牛刀。以后,就请你陈设贰个简短的算法消除那个难题。

输入输出格式

输入格式:

 

第一行三个整数n,表示他们各有几匹马(五人有着的马的数额同样)。第二行n个整数,每一种整数都表示田期思的某匹马的速度值(0
<= 速度值<=
100)。第三行n个整数,描述齐王的马的速度值。两马相遇,依照速度值的高低就足以驾驭哪匹马会胜出。假若速度值同样,则和局,什么人也不拿钱。

【数据规模】

4858.com,对于20%的数据,1<=N<=65;

对于40%的数据,1<=N<=250;

对于100%的数据,1<=N<=2000。

 

输出格式:

 

仅一行,三个整数,表示田期思最大能收获多少银币。

 

输入输出样例

输入样例#1:

392 83 7195 87 74

输出样例#1:

200

 1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<stack> 5 #include<algorithm> 6 #include<cstring> 7 #include<string> 8 #include<vector> 9 #include<cmath>10 using namespace std;11 const int inf=1e9;12 int n,t[2010],q[2010];13 int read()14 {15     int ans=0,x=1;char ss=getchar();16     while(ss<'0'||ss>'9'){if(ss=='-') x=-1;ss=getchar();}17     while(ss>='0'&&ss<='9'){ans=ans*10+ss-'0';ss=getchar();}18     ans*=x;return ans;19 }20 int pk(int x[],int y[])21 {22     int h1=1,h2=1,t1=n,t2=n,ans=0;23     for(int i=1;i<=n;++i)//比n场 24     {25         if(x[t1]>y[t2]){--t1;--t2;ans+=200;continue;}//最快的马比对手最慢的马快26         if(x[h1]>y[h2]){++h1;++h2;ans+=200;continue;}//最慢的马比对手最快的马快27         if(x[t1]==y[h2]){--t1;++h2;continue;}//最快的马比对手最慢的马快 28         ++h1;--t2;ans-=200;//均不符合,用最慢的马消耗对手最快的马 29     }30      return ans; 31 }32 int main()33 {34     scanf("%d",&n);35     for(int i=1;i<=n;++i) t[i]=read();36     for(int i=1;i<=n;++i) q[i]=read();37     sort(t+1,t+n+1);sort(q+1,q+n+1);38     printf("%d\n",pk;39     return 0;40 }

输入输出样例

输入样例#1:

3
92 83 71
95 87 74

输出样例#1:

200

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<string>
 8 #include<vector>
 9 #include<cmath>
10 using namespace std;
11 const int inf=1e9;
12 int n,t[2010],q[2010];
13 int read()
14 {
15     int ans=0,x=1;char ss=getchar();
16     while(ss<'0'||ss>'9'){if(ss=='-') x=-1;ss=getchar();}
17     while(ss>='0'&&ss<='9'){ans=ans*10+ss-'0';ss=getchar();}
18     ans*=x;return ans;
19 }
20 int pk(int x[],int y[])
21 {
22     int h1=1,h2=1,t1=n,t2=n,ans=0;
23     for(int i=1;i<=n;++i)//比n场 
24     {
25         if(x[t1]>y[t2]){--t1;--t2;ans+=200;continue;}//最快的马比对手最慢的马快
26         if(x[h1]>y[h2]){++h1;++h2;ans+=200;continue;}//最慢的马比对手最快的马快
27         if(x[t1]==y[h2]){--t1;++h2;continue;}//最快的马比对手最慢的马快 
28         ++h1;--t2;ans-=200;//均不符合,用最慢的马消耗对手最快的马 
29     }
30      return ans; 
31 }
32 int main()
33 {
34     scanf("%d",&n);
35     for(int i=1;i<=n;++i) t[i]=read();
36     for(int i=1;i<=n;++i) q[i]=read();
37     sort(t+1,t+n+1);sort(q+1,q+n+1);
38     printf("%d\n",pk(t,q));
39     return 0;
40 }

 

输入输出格式

输入格式:

率先行贰个平头n,表示他们各有几匹马(几个人具备的马的数码一样)。第二行n个整数,每一种整数都代
表田忌的某匹马的进程值(0 <= 速度值<=
100)。第三行n个整数,描述齐王的马的快慢值。两马相遇,根据速度值的大大小小就足以通晓哪匹马会胜出。假使速度值同样,则和局,何人也不拿钱。

【数据规模】

对于20%的数据,1<=N<=65;

对于40%的数据,1<=N<=250;

对于100%的数据,1<=N<=2000。

输出格式:

仅一行,三个大背头,表示田忌最大能获得多少银币。

输入输出样例

输入样例#1:

3
92 83 71
95 87 74

输出样例#1:

200

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<string>
 8 #include<vector>
 9 #include<cmath>
10 using namespace std;
11 const int inf=1e9;
12 int n,t[2010],q[2010];
13 int read()
14 {
15     int ans=0,x=1;char ss=getchar();
16     while(ss<'0'||ss>'9'){if(ss=='-') x=-1;ss=getchar();}
17     while(ss>='0'&&ss<='9'){ans=ans*10+ss-'0';ss=getchar();}
18     ans*=x;return ans;
19 }
20 int pk(int x[],int y[])
21 {
22     int h1=1,h2=1,t1=n,t2=n,ans=0;
23     for(int i=1;i<=n;++i)//比n场 
24     {
25         if(x[t1]>y[t2]){--t1;--t2;ans+=200;continue;}//最快的马比对手最慢的马快
26         if(x[h1]>y[h2]){++h1;++h2;ans+=200;continue;}//最慢的马比对手最快的马快
27         if(x[t1]==y[h2]){--t1;++h2;continue;}//最快的马比对手最慢的马快 
28         ++h1;--t2;ans-=200;//均不符合,用最慢的马消耗对手最快的马 
29     }
30      return ans; 
31 }
32 int main()
33 {
34     scanf("%d",&n);
35     for(int i=1;i<=n;++i) t[i]=read();
36     for(int i=1;i<=n;++i) q[i]=read();
37     sort(t+1,t+n+1);sort(q+1,q+n+1);
38     printf("%d\n",pk(t,q));
39     return 0;
40 }

 

标题描述
国内历史上有个著名的传说:
那是在2300年以前。唐宋的太傅田期思喜欢赛马。他时时和齐王赛马。他…

输入输出样例

输入样例#1:

3
92 83 71
95 87 74

出口样例#1:

200

这是一道让人吐血的好题。。

先来想想贪心策略(这里一定要理清思路,慢慢来,别急):
如果总是用最弱的马 去打对面最强的马,可能不是最优,因为这里有平局的情况存在,选择平局可能比赢给最强的马更合算
(譬如:田忌 2 3 10  齐威王:2 8 9)
因此,我们要这样去分析:
先看最弱的马之间的实力,如果我方最弱的马比对方最弱的马强,就直接怼掉。这个比较显然,既然我方最弱的马更强,那么我方其它马一定可以怼掉对方最弱的马,但杀鸡焉用牛刀?
如果我方的马比对方的马弱或者相等:
有一种策略是用最弱的马去怼最强的马,让“炮灰”的作用发挥到极值,
另一种策略是先看最强的马之间的关系。

我们来分别讨论这两种策略,并证明两种策略都是正确的:

1、用最弱的马去怼最强的马,这样输了一盘,但这一盘是早晚要输的。如果最弱的马等于对方最弱的马,那么怼掉对方最强马,一定有其它马可以赢回来;如果最弱的马小于对方最弱的马,那么必然小于对方所有马,这是必然的。因此应让它去怼掉对方最强的,让我放最强的能够成功得分道路进一步开阔。
2、先看最强的马之间的关系。如果我方最强马比对方更强,就怼掉,否则就应该让最弱的马去怼对方最强的马。因为我方最强的马虽然打不过敌方最强马,但说不定可以打过第二强、第三强……但是最弱的马却一定赢不了所有的马。
两条结合着来,差不多了就。。。
但是还有一种特殊情况:最弱的马平局,最强的马平局,且最弱的马等于最强的马
这时所有对决均为平局,直接输出答案即可。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))
#define lowbit(a) ((a) & (-(a)))

int read()
{
    int x = 0;char ch = getchar();char c = ch;
    while(ch > '9' || ch < '0')c = ch, ch = getchar();
    while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
    if(c == '-')return -x;
    return x;
}
const int INF = 0x3f3f3f3f;
const int MAXN = 2000 + 10;

int n,tian[MAXN],qi[MAXN];
int ans;


inline void init()
{
    n = read();
    for(int i = 1;i <= n;i ++)
    {
        tian[i] = read();
    }
    std::sort(tian + 1, tian + 1 + n);
    for(int j = 1;j <= n;j ++)
    {
        qi[j] = read();
    }
    std::sort(qi + 1, qi + 1 + n);
}
inline void put()
{
    printf("%d", ans * 200);
}
inline void tan()
{
    int head1 = 1,tail1 = n,head2 = 1,tail2 = n;
    while(head1 <= tail1)
    {
        if(tian[head1] > qi[head2]) head1 ++,head2 ++,ans ++; 
        else if(tian[head1] < qi[head2]) head1 ++,tail2 --,ans --;
        else//平局
        {
            if(tian[tail1] > qi[tail2])tail1 --, tail2 --, ans ++;
            else if(tian[head1] < qi[tail2])head1 ++, tail2 --, ans--;//注意!!
            else break;
        }
    }
}

int main()
{
    init();
    tan();
    put();
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 美高梅手机版4858 版权所有