田忌赛马 解题报告

描述：

田忌与齐王赛马，双方各有n匹马参赛（n<=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。

输入：

多个测例。
每个测例三行：第一行一个整数n，表示双方各有n匹马；第二行n个整数分别表示田忌的n匹马的速度；第三行n个整数分别表示齐王的n匹马的速度。
n＝0表示输入结束。

输出：

每行一个整数，田忌最多能赢多少两黄金。

输入样例：

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
3
20 20 10
20 20 10
0

输出样例：

1
0
0
0

解题思路：先把田忌与齐王的马的速度进行由小到大的排序，然后用田忌的慢马去和齐王的快马先比较，一直找到比齐王的马快中的最快的并标记已比过，这样就可以保证田忌的马能够达到合理的利用，可以贪到更多的赢的场次，然后就是求出它们平局的场数并标记，用总数减去他们就是输的场数，从而就可以得出了。

代码如下：

#include<iostream>
#include<algorithm>

usingnamespacestd;
#defineMAX106
structspeed
{
intdata;
intstate;
};

intcmp(speeda,speedb)
{
if(a.data<b.data)return1;
elsereturn0;
}
intmain()
{
intn;
speednum1[MAX],num2[MAX];
cin>>n;
while(n)
{
for(inti=0;i<n;i++)
{
cin>>num1[i].data;
num1[i].state=0;
}
for(i=0;i<n;i++)
{
cin>>num2[i].data;
num2[i].state=0;
}
sort(num1,num1+n,cmp);
sort(num2,num2+n,cmp);
signedintsum1=0,sum2=0;
for(i=0;i<n;i++) //这边的目的是求出赢的场数
{
for(intj=n-1;j>=0;j--)
{
if(num1[i].data>num2[j].data)
{
if(num1[i].state==0&&num2[j].state==0)
{
sum1++;
num1[i].state=1;
num2[j].state=1;
break;
}
}
}
}
for(i=0;i<n;i++) //这边的额目的是求出平局的场数
{
for(intj=0;j<n;j++)
{
if(num1[i].data==num2[j].data)
{
if(num1[i].state==0&&num2[j].state==0)
{
sum2++;
num1[i].state=1;
num2[j].state=1;
break;
}
}
}
}
cout<<2*sum1-n+sum2<<endl;
cin>>n;
}
return0;
}