欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2014牡丹江——Known Notation

程序员文章站 2024-03-22 17:02:46
...

题目链接

  • 题意:
    输入一个长度不超过1000的字符串,包含数字(1-9)和星号(*)。字符串中的空格已经丢失,所以连起来的数字串能够看成很多分开的数。也能够看成连续的数,即能够随意加入空格。

    如今有两种操作:1)在任何位置加入随意类型的字符(数字或者星号)    2)交换字符串中的随意两个字符
    求:最少操作多少次,使得得到的串是一个合法的逆波兰式

  • 分析:
    对于n个星号,n+1个数字的字符串,假设将星号都移动到串的末尾。那么一定是合法的
    对于操作1,假设须要插入数字,那么插入到字符串的最前边是最优的
    对于操作2,仅仅可能将星号和数字交换。而且将星号移到了字符串的后边

    那么,先对串进行操作1,使得数字个数不小于星号的个数加一;然后从左到右扫描字符串,假设当前星号前边的数字和星号不满足相应关系(同上)。须要将当前星号与最后一个数字交换;最后,假设字符串最后不是星号。答案加一
  • 注意:
    假设最后得到的串最后不是星号。那么必定答案加一
    假设输入没有星号。那么答案是0
const int maxn = 1100;

char s[maxn];
int n;
vector<int> v;
int main()
{
    int T;
    RI(T);
    while (T--)
    {
        v.clear();
        RS(s);
        n = strlen(s);
        int num = 0, sig = 0;
        REP(i, n)
        {
            if (s[i] == '*') sig++;
            else
            {
                v.push_back(i);
                num++;
            }
        }
        int ans = 0;
        int preadd = 0;
        if (!sig)
        {
            ans = 0;
        }
        else
        {
            if (num < sig + 1)
            {
                preadd = sig + 1 - num;
                ans += preadd;
            }


            int sig_num = 0;

            for (int i = 0; i < n; i++)
            {
                if (s[i] == '*')
                {
                    sig_num++;
                    if (preadd < sig_num + 1)
                    {
                        int sz = v.size();
                        int id = v[sz - 1];
                        v.pop_back();
                        swap(s[i], s[id]);

                        sig_num--;
                        preadd++;
                        ans++;
                    }
                }
                else preadd++;
            }


            if (s[n - 1] != '*')
                ans++;
        }
        printf("%d\n", ans);

    }
    return 0;
}