题目链接:zoj 3829 Known Notation
题目大意:给定一个不完整的后缀表达式,要求有2种不同操作,用尽量少的操作使得表达式完整。
解题思路:贪心,数字的个数要要保证比∗的个数多1,不够的话优先补在开头是最优的。然后遍历一遍字符串,碰到数字+1,碰到∗-1,保证数字的个数大于等1,如果不够减的话,可以和最后面的一个数字交换位置(用栈维护十分方便),因为添加和交换代价都是1。
不过这题数据实在够弱的,因为11∗1这种情况,至少需要添加一个∗号才可以(特判即可),但是居然也可以过,同步赛的时候因为考虑了这个还WA了一次,因为11的情况还是为0的。
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn = 1005;
char s[maxn];
int solve () {
stack<int> sta;
int len = strlen(s), c = 0;
for (int i = 0; i < len; i++) {
if (s[i] == '*')
c++;
else
sta.push(i);
}
if (c == 0)
return 0;
int n = len - c;
int ret = n = max(c + 1 - n, 0);
for (int i = 0; i < len; i++) {
if (s[i] == '*') {
if (n <= 1) {
s[sta.top()] = '*';
sta.pop();
n++;
ret++;
} else
n--;
} else
n++;
}
if (ret == 0 && s[len-1] != '*')
ret++;
return ret;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%s", s);
printf("%d\n", solve());
}
return 0;
}
分享到:
相关推荐
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
zoj 2536 这个不是用贪心做的
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj吐血制作,希望大家喜欢