ZOJ 3829 [贪心]

题目

Known Notation

题意

题目给出一个字符串,其由非零的数字(1~9)和*号组成。

现在有两种操作:

Insert:可以在字符串中任意位置插入一个1~9的数字。

Swap:可以交换字符串中任意两个字符。

现在要求是对于给定字符串进行以上两种操作,使得字符串符合逆波兰表达式。

例如2*3*4可以先在最前面Insert一个1,构成字符串12*3*4,然后swap最后两个数,得到字符串12*34*,这个字符串就符合逆波兰表达式(RNP)。

输入

第一行给出测试组数T

接下来是T行,每行一个字符串。

输出

输出最小所需的操作数

样例输入

3
1*1
11*234**
*

样例输出

1
0
2

题解分析

其实当时比赛的时候看到这道题,觉得很亲切,因为之前学栈的时候有专门学习了一下逆波兰,不过这道题不需要用到栈,很可惜比赛没做出来,自己还是太菜了。

思路就是逆波兰跟原式相比,只少了括号以及改变了操作符的顺序,那么意味着:

操作符的数量一定是小于数字的数量的。

其次就是分情况讨论,当数字的数量 ≤ 操作符数量的时候,肯定至少Insert缺少的数量

然后当数字数量足够的时候,只需要进行Swap操作。

所以流程就是,首先统计一下数量,然后用一个add变量储存Insert操作的数量,之后遍历一遍字符串,如果遇到数字,那么数字的数量+1,如果遇到的是*号,那么星号的数量+1,如果数字数量≤星号的数量,并且能够Insert,那么就直接Insert,这时候数字的数量+1,add变量-1,如果Insert操作数量用光了,那就只能Swap了,交换当前遇到的星号和之后的某个数字,相当于目前遍历到的数字+1,遇到的星号数量-1。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(void)
{
int T;
char s[2000];
scanf("%d",&T);
getchar();
while(T--)
{
scanf("%s",s);
int len = strlen(s);
int op=0, num=0;
int res=0;
for(int i=0;i<len;i++)
{
if(s[i]=='*')
op++;
else num++;
}
int add=0;
if(num<=op)
{
add = (op-num)+1;
res+=add;
}
op = num = 0;
for(int i=0;i<len;i++)
{
if(s[i]!='*')
num++;
else
{
op++;
if(num<=op)
{
if(add)
{
add--;
num++;
}
else
{
res++;
num++;
op--;
}
}
}
}
cout<<res<<endl;
}
return 0
}