算法题目——田忌赛马(POJ-2287)

拼搏现实的明天。 2022-09-10 15:29 156阅读 0赞

[POJ-2287][]  
[参考文章][Link 1]

#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;
    	}
    
     }

[POJ-2287]: http://poj.org/problem?id=2287
[Link 1]: https://blog.csdn.net/qq_52480906/article/details/114214764