本文主要是介绍zoj 3829 (2014牡丹江区域赛K) Known Notation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给一个不带空格的逆波兰式，问最少进行几次操作，能使这个式子合法。操作有两种：在任意位置插入一个字符（数字或运算符），交换任意两个字符。
思路：贪心。分析一下可以知道，合法的逆波兰式数字至少比运算符多1，那么可以先通过插入让式子满足这个条件，剩下的都用交换解决（用交换解决需要的次数不会大于插入）。对于第一步，我们可以贪心都插入在最前面；对于第二步，我们可以贪心把最前面的运算符与最后面的数字交换。其实不需要真正执行两种操作，只需要计数就可以了。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#include <sstream>
#define INF 1000000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010 using namespace std; char str[1010];int main(){int t;cin>>t;while(t--){scanf("%s",str);int siz=strlen(str);int cntn=0;int cnto=0;for(int i=0;i<siz;i++){ //统计需要插入多少个数字 if(str[i]=='*') cnto++;else cntn++;}int add=0;if(cnto>cntn-1)add=cnto-cntn+1;cntn=add; cnto=0;int swap=0;for(int i=0;i<siz;i++){if(str[i]=='*') cnto++;else cntn++;if(cnto>cntn-1){ //如果当前不合法了,"交换"一下 swap++;cnto--;cntn++;}}cout<<add+swap<<endl;}return 0;
}这篇关于zoj 3829 (2014牡丹江区域赛K) Known Notation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
