C++解决田忌赛马问题

解题思路:

1. 将双方马的速度放入矢量

2. 将双方马的速度进行排序

3. 逐一对比速度，记k为胜场

4. 如果胜场超过一半则输出结果

5. 如果不足一半则将老王马的速度整体前移1个位置，有一次超过则输出YES，否则继续循环

6. 当超过循环次数到n时flag仍为0则判断失败，输出NO
   

注意事项:

别把k=0的位置放错（失败教训了属于是）

参考代码:

#include#include#includeusing namespace std;
int main()
{
	int n;
	while (cin >> n)
	{
		if (n == 0)
		{
			break;
		}
		else
		{
			vector a1;
			vector a2;
			int m;
			for (int i = 0; i < n; i++)//将数据填入vector数组
			{
				cin >> m;
				a1.push_back(m);
			}
			for (int i = 0; i < n; i++)
			{
				cin >> m;
				a2.push_back(m);
			}
			int k;
			int x = 0;
			sort(a1.begin(), a1.end());//分别对两个数组从小到大排序
			sort(a2.begin(), a2.end());
			int flag = 0;
			while (x < n)
			{
				k = 0;
				for (int t = 0; t < n; t++)
				{
					if (a1[t] > a2[t])
					{
						k += 1;
					}
				}
				if (k > n / 2)//如果成立则直接输出
				{
					cout << "YES" << endl;
					flag = 1;
					break;
				}
				else//不成立则将老王的数组整体前移一位
				{
					int y = a1[0];
					for (int i = 0; i < n - 1; i++)
					{
						a1[i] = a1[i + 1];
						a1[n - 1] = y;
					}
					x += 1;//测试次数+1
				}
			}
			if (flag == 0)//如果无法成立，输出NO
			{
				cout << "NO" << endl;
			}
		}
	}
}