hdu 3351

题意：给出一个由'{' , '｝' 组成的字符串，通过改变最少括号的方向使其匹配。

思路：贪心方法：从左向右遍历，遇到左括号lef++，遇到右括号，若lef>0，lef--，否则右括号变为左括号，ans++，lef++，最后再加上多下来的左括号，即lef/2。

代码如下：

 * 3351_2.cpp 
 * 
 *  Created on: 2013年8月7日 
 *      Author: Administrator 
 */  
  
  
  
  
#include <iostream>   
  
using namespace std;  
  
  
int main(){  
  
    string str;  
    int lef;  
    int ans;  
    int count = 1;  
    while( cin >> str,str[0]!= '-'  ){  
  
        lef = 0,ans =0;  
        for(int i = 0 ; i < str.length() ; ++i ){  
            if(str[i] == '{'){//如果是左括号   
                lef++;  
            }else if(lef > 0 ){//如果是右括号且左括号的数量>0   
                --lef;  
            }else{//如果是右括号且左括号的数量<=0   
                //是右括号转向成左括号   
                ans++;  
                lef++;  
            }  
        }  
  
        cout<<count++<<". "<<(ans+lef/2)<<endl;  
    }  
  
}  

补充：软件开发 , C++ ,

上一个：hdu 1548 A strange lift
下一个：查找单链表的中点