算法題目——田忌賽馬(POJ-2287)

POJ-2287

參考文章

#include<iostream>
#include<vector>


#include<algorithm>
#include<cstring> 
using namespace std;
bool comp(int x ,int y)
{
    return x > y;
}
int main()
{
	int n;
	int temp;//儲存臨時變量的 
	vector<int> vec;//用于儲存輸出的結果 
	while(cin>>n&&n!=0)
	{
		vector<int> tian_vec;
		vector<int> qi_vec;
		
		for(int i=0;i<n;i++)
		{
			cin>>temp;
			tian_vec.push_back(temp); 
		}
		sort(tian_vec.begin(),tian_vec.end(),comp);
		for(int i=0;i<n;i++)
		{
			cin>>temp;
			qi_vec.push_back(temp);
		}
		sort(qi_vec.begin(),qi_vec.end(),comp);
		
		
		int tian_i=0;
		int tian_j=tian_vec.size()-1;
		int qi_i=0;
		int qi_j=qi_vec.size()-1;
		int num=0;//記錄田忌赢的次數 
		int lost=0;//記錄田忌輸的次數 
		
		for(int i=0;i<n;i++)
		{
			if(tian_vec[tian_i]>qi_vec[qi_i])//田忌的優等馬>齊王的優等馬
			{
				num++;
				tian_i++;
				qi_i++; 
			}
			else//田忌的優等馬<=齊王的優等馬
			{
				if(tian_vec[tian_j]>qi_vec[qi_j])//田忌的下等馬>齊王的下等馬
				{
					num++;
					tian_j--;
					qi_j--;
				}
				else//田忌的下等馬<=齊王的下等馬,田忌的下等馬去比較齊王的上等馬 
				{
					
					if(tian_vec[tian_j]<qi_vec[qi_i])//田忌的下等馬<齊王的上等馬
					{
						num--; 
						tian_j--;
						qi_i++;
					} 
					
				 
					
					 
				 }
				
				
			}
			
			
		}
		
		tian_vec.clear();
		qi_vec.clear();
			vec.push_back(num*200);
	}
	for(int i=0;i<vec.size();i++)
	{
		cout<<vec[i]<<endl;
	}

 }