田忌赛马

NC231619. 田忌赛马

描述

田忌赛马是大家耳熟能详的故事，也是运筹学中的经典案例。

假设，齐国大将田忌和齐威王约定赛马，这次比赛共 $n$ 回合，谁获胜的回合数多谁取得最终的胜利。两人各有 $n$ 匹马，每回合由双方各派出一匹马比赛（同一匹马只能派出一次）。

如果田忌已经知道了这 $2n$ 匹马的速度值（赛马的时候总是速度值高的获胜）和齐王派出马比赛的顺序，并且他可以自由选择自己的马的比赛顺序。为了向齐威王展示自己的运筹能力，田忌想要赢得尽可能多的回合数，请问田忌最多能够赢得多少回合的胜利。

输入描述

首先，第一行是一个整数 ，代表总共有  组独立的测试数据。

然后是  组测试数据，每组测试数据有三行，

第一行一个整数 ，代表双方各自有多少匹马。

第二行  个整数 , , ,... ,，代表田忌派出参赛的  匹马的速度值，

第三行  个整数 , , ,... ,，代表齐威王派出参赛的  匹马的速度值。

* 
* 
*  ()。
* 保证 ， ( 如果  )，且  ()

输出描述

每组测试数据输出一行，每行一个整数代表在该测试数据中田忌最多能赢得的回合数。

示例1

输入:

2
3
2 3 5
1 4 6
5
1 3 5 7 10
4 8 9 11 15

输出:

2
2

说明:

第一组样例中，田忌以速度值为 2 的马迎战齐威王速度值为 6 的马，输掉一回合；田忌以速度值为 3 的马迎战齐威王速度值为 1 的马，赢下一回合；田忌以速度值为 5 的马迎战齐威王速度值为 4 的马，赢下一回合，最终获得 2 回合的胜利。

第二组样例中，田忌最多赢得 2 回合的胜利。田忌以速度值为 10 的马迎战齐威王速度值为 9 的马，以速度值为 7 的马迎战速度值为 4 的马，获得 2 回合的胜利。另外，田忌以速度值为 10 的马迎战齐威王速度值为 9 的马，以速度值为 5 的马迎战速度值为 4 的马，获得 2 回合的胜利；田忌以速度值为 10 的马迎战齐威王速度值为 8 的马，以速度值为 5 的马迎战速度值为 4 的马，获得 2 回合的胜利等方案都是可行的。而且可以通过枚举证明，在这一组数据中田忌不可能赢得超过 2 回合的胜利。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3 解法, 执行用时: 225ms, 内存消耗: 38304K, 提交时间: 2022-04-05 01:07:57

for T in range(int(input())):
    n = int(input())
    a = [0]+sorted(list(map(int,input().split())),reverse = True)
    b = [0]+sorted(list(map(int,input().split())),reverse = True)
    i = 1
    j = 1
    while i<n+1 and j <n+1:
        if b[j]<a[i]:
            i+=1
            j+=1
        else:
            j+=1
    print(i-1)

C++ 解法, 执行用时: 16ms, 内存消耗: 396K, 提交时间: 2022-04-10 20:41:17

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t,n;
	cin>>t;
	while(t--){
		int p=0,c=0,a[105],b[105];
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		for(int i=0;i<n;i++){
			cin>>b[i];
		}
		for(int i=0;i<n;i++){
			if(a[i]>b[p]){
				p++;
				c++;
			}
		}
		cout<<c<<endl;
	}
}

Python3 解法, 执行用时: 60ms, 内存消耗: 4656K, 提交时间: 2022-04-10 13:22:00

t=int(input())
for T in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    j=0
    c=0
    for i in range(n):
        if a[i]>b[j]:
            j=j+1
            c=c+1
    print(c)

上一题

下一题

详情