华师一附中OI组

标题: P1650 田忌赛马 [打印本页]

---

作者: admin    时间: 2018-6-29 18:22
标题: P1650 田忌赛马
https://www.luogu.org/problemnew/show/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。

输出格式：
仅一行，一个整数，表示田忌最大能得到多少银币。

输入输出样例
输入样例#1：
3
92 83 71
95 87 74
输出样例#1：
200

---

作者: 黄煦喆    时间: 2018-7-27 20:37

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int i,n,k1,k2,p1,p2,sum;
   
5. int a[2020],b[2020];
   
6. int main()
   
7. {
   
8.     cin>>n;
   
9.     for(i=1; i<=n; i++)cin>>a[i];
   
10.     for(i=1; i<=n; i++)cin>>b[i];
    
11.     sort(a+1,a+n+1);
    
12.     sort(b+1,b+n+1);
    
13.     sum=0;
    
14.     k1=k2=1;
    
15.     p1=p2=n;
    
16.     while(k1<=p1)
    
17.         if(a[k1]>b[k2])
    
18.         {
    
19.             k1++;
    
20.             k2++;
    
21.             sum++;
    
22.         }
    
23.         else if(a[k1]<b[k2])
    
24.         {
    
25.             k1++;
    
26.             p2--;
    
27.             sum--;
    
28.         }
    
29.         else
    
30.         {
    
31.             if(a[p1]>b[p2])
    
32.             {
    
33.                 p1--;
    
34.                 p2--;
    
35.                 sum++;
    
36.             }
    
37.             else if(a[p1]<b[p2])
    
38.             {
    
39.                 k1++;
    
40.                 p2--;
    
41.                 sum--;
    
42.             }
    
43.             else
    
44.             {
    
45.                 if(a[k1]<b[p2])sum--;
    
46.                 k1++,p2--;
    
47.             }
    
48.         }
    
49.     cout<<sum*200<<endl;
    
50.     return 0;
    
51. }
    

复制代码

---

作者: 张笑宇    时间: 2018-7-27 22:08

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n,i;
   
5. const int mx=2010;
   
6. int t[mx],w[mx];///田忌 王
   
7. int thead,ttail,whead,wtail;
   
8. int main()
   
9. {
   
10.     cin>>n;
    
11.     for (i=1; i<=n; i++) cin>>t[i];
    
12.     for (i=1; i<=n; i++) cin>>w[i];
    
13.     sort(t+1,t+n+1);
    
14.     sort(w+1,w+n+1);
    
15.     thead=whead=n,ttail=wtail=1;
    
16.     int sum=0;
    
17.     while (thead>=ttail && whead>=wtail)
    
18.     {
    
19.         if (t[thead]>w[whead])
    
20.         {
    
21.             sum++;
    
22.             thead--;
    
23.             whead--;
    
24.         }
    
25.         else if (t[thead]<w[whead])
    
26.         {
    
27.             sum--;
    
28.             whead--;
    
29.             ttail++;
    
30.         }
    
31.         else ///大马相等的情况
    
32.         {
    
33.             ///以下是小马
    
34.             if (t[ttail]>w[wtail])///
    
35.             {
    
36.                 sum++;
    
37.                 ttail++;
    
38.                 wtail++;
    
39.             }
    
40.             else
    
41.             {
    
42.                 if (w[whead]>t[ttail])
    
43.                 {
    
44.                     sum--;
    
45.                 }
    
46.                 whead--;
    
47.                 ttail++;
    
48. 
    
49. 
    
50.             }
    
51. 
    
52.         }
    
53.     }
    
54.     cout<<sum*200;
    
55.     return 0;
    
56. }
    

复制代码

---

作者: 七夜劫年    时间: 2018-7-27 22:44
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 2005
#define inf 0x7fffffff
int n,a[maxn],b[maxn];

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
            cin>>b[i];
        }

        sort(a+1,a+n+1);
        sort(b+1,b+n+1);

        int sum=0;

        for(int la=1,ra=n,lb=1,rb=n;la<=ra&&lb<=rb;)
        {
            if( a[la] > b[lb] )
            {
                la++,lb++,sum++;
            }
            else if( a[la] < b[lb] )
            {
                la++,rb--,sum--;
            }
            else if( a[ra] > b[rb] )
            {
                ra--,rb--,sum++;
            }
            else
            {
                sum-=a[la]!=b[rb],la++,rb--;
            }
        }
        printf("%d\n",sum*200);
    }
    return 0;
}

---

作者: 吴语林    时间: 2018-7-29 19:37

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n,a[3000],b[3000],f[3000][3000],ans=-0x3f3f3f3f;
    
14. bool cmp(int x,int y)
    
15. {
    
16.         return x>y;
    
17. }
    
18. int main()
    
19. {
    
20.         scanf("%d",&n);
    
21.         for(int i=1;i<=n;i++)
    
22.                 scanf("%d",&a[i]);
    
23.         for(int i=1;i<=n;i++)
    
24.                 scanf("%d",&b[i]);
    
25.         sort(a+1,a+1+n,cmp);sort(b+1,b+1+n,cmp);
    
26.         for(int i=1;i<=n;i++)
    
27.         {
    
28.                 int x1,x2;
    
29.                 if(a[n-i+1]>b[i])
    
30.                         x1=200;
    
31.                 else if(a[n-i+1]==b[i])
    
32.                         x1=0;
    
33.                 else
    
34.                         x1=-200;
    
35.                 f[i][0]=f[i-1][0]+x1;
    
36.                 for(int j=1;j<=i;j++)
    
37.                 {
    
38.                         if(a[n-(i-j)+1]>b[i])
    
39.                                 x1=200;
    
40.                         else if(a[n-(i-j)+1]==b[i])
    
41.                                 x1=0;
    
42.                         else
    
43.                                 x1=-200;
    
44.                         if(a[j]>b[i])
    
45.                                 x2=200;
    
46.                         else if(a[j]==b[i])
    
47.                                 x2=0;
    
48.                         else
    
49.                                 x2=-200;
    
50.                         f[i][j]=max(f[i-1][j]+x1,f[i-1][j-1]+x2);
    
51.                 }
    
52.         }
    
53.         for(int i=0;i<=n;i++)
    
54.                 ans=max(ans,f[n][i]);
    
55.         printf("%d",ans);
    
56.     return 0;
    
57. }

复制代码

---

作者: 倚窗倾听风吹雨    时间: 2018-9-28 18:13

1. #include<iostream>
   
2. #include<algorithm>
   
3. #define FOR(i,a,b) for(int i=a;i<=b;i++)
   
4. using namespace std;
   
5. const int N=2005;
   
6. int n,tj[N],qw[N],ans,i,j,ii,jj;
   
7. int main()
   
8. {
   
9.     cin>>n;FOR(i,1,n)cin>>tj[i];FOR(i,1,n)cin>>qw[i];
   
10.     sort(tj+1,tj+n+1,greater<int>());sort(qw+1,qw+n+1,greater<int>());
    
11.     i=1;j=1;ii=n;jj=n;
    
12.     while(i<=ii)
    
13.     {
    
14.         if(tj[i]>qw[j]){ans+=200;i++;j++;continue;}
    
15.         else if(tj[i]<qw[j]){ans-=200;ii--;j++;continue;}
    
16.         else
    
17.         {
    
18.             if(tj[ii]>qw[jj]){ans+=200;ii--;jj--;continue;}
    
19.             else if(tj[ii]<qw[j]){ans-=200;ii--;j++;continue;}
    
20.         }
    
21.         i++,j++;
    
22.     }
    
23.     cout<<ans<<endl;
    
24.     return 0;
    
25. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2