科林明伦杯

E 赛马

链接:https://ac.nowcoder.com/acm/contest/5758/E
来源:牛客网

题目描述

一天小明与他同学准备赛马,他们每人有n匹马,每匹马有一个固定的战力值,战力值高的马会战胜战力值低的马并赢得比赛。每匹马只能出场比赛一次。小明偷看到了他对手每匹马的出场顺序,小明在更改自己马出场顺序后最多能赢多少场比赛。

输入描述:

输入t,代表有t组数据。每组数据输入正整数n,每人的马匹数量。下一行输入n个值a[i],代表小明每匹马的战力值。接下来一行输入n个值b[i],代表对手按顺序出场的每匹马的战力值。(t<=10, n<1000,1<=i<=n,a[i]<1e6,b[i]<1e6)

输出描述:

小明在更改马匹出场顺序后,最多能赢的场数。

输入

1
3
5 8 8
4 7 10

输出

2

我的代码

#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,ans=0;
		int a[1001],b[1001];
		scanf("%d",&n);
		for (int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		for (int i=0;i<n;i++)
		{
			scanf("%d",&b[i]);
		}
		sort(a,a+n,cmp);
		sort(b,b+n,cmp);
		int k=0,able=0;
		for (int i=0;i<n;i++)
		{
			while(a[k]>b[i]&&k<n)
			{
				able++;
				k++;
			}
			if (able>0)
			{
				able--;
				ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

发表评论