当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

zoj 3829 Known Notation(贪心)

发表于: 2014-10-13   作者:阿尔萨斯   来源:转载   浏览:
ZOJ
摘要: 题目链接:zoj 3829 Known Notation 题目大意:给定一个不完整的后缀表达式,要求有2种不同操作,用尽量少的操作使得表达式完整。 解题思路:贪心,数字的个数要要保证比∗的个数多1,不够的话优先补在开头是最优的。然后遍历一遍字符串,碰到数字+1,碰到∗-1,保证数字的个数大于等1,如果不够减的话,可以和最后面的一个数字交换位置(用栈维护十分方便),因为添加和交换代价都是1

题目链接:zoj 3829 Known Notation

题目大意:给定一个不完整的后缀表达式,要求有2种不同操作,用尽量少的操作使得表达式完整。

解题思路:贪心,数字的个数要要保证比的个数多1,不够的话优先补在开头是最优的。然后遍历一遍字符串,碰到数字+1,碰到-1,保证数字的个数大于等1,如果不够减的话,可以和最后面的一个数字交换位置(用栈维护十分方便),因为添加和交换代价都是1。
不过这题数据实在够弱的,因为111这种情况,至少需要添加一个号才可以(特判即可),但是居然也可以过,同步赛的时候因为考虑了这个还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 3829 Known Notation(贪心)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Pass-Muraille Time Limit: 2 Seconds Memory Limit: 65536 KB In modern day magic shows, passing
use the function findHomography to find the transform between matched keypoints. use the func
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器
题目链接:http://www.patest.cn/contests/pat-a-practise/1073 题目: Scientific notation is the
在进行数据库设计模型时,分为概念模型设计和物理模型设计两种,概念模型主要是反映真是世界中的业
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。它基于JavaScript(Standard ECMA-
1. BPMN(Business Process Modeling Notation)业务流程建模符号。 2. BPMI(The Business Process Ma
在Android5.0的源码中编译apk会出现如下的问题 libpng warning: "iCCP: Not recognizing known sRGB
这个是ssh基本操作的连接,当你配置完ssh之后,然后明明是正确的,然后你使用命令: ssh localhost
Multi-Touch Systems that I Have Known and Loved LINK: http://www.billbuxton.com/multitouchOve
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号