A题有两种方法:
第一种是把-1替换成0,1,2做测试;
第二种是把-1替换成0,1做测试,对于-1替换成1的情况,要额外用bool值记录当前使用的数字是否由-1所替换成的那个1得来。

第一种方法:

/*12ms*/

class Suminator
{
    public:
        ll cal(vector <int> program, int x)
        {
            int n = program.size();
            For(i, n) if (program[i] == -1) program[i] = x;
            stack<ll> S;
            For(i, 100) S.push(0); //push enough zeroes in stack S, infact, n + 2 is enough.
         For(i, n)
            if (program[i]) S.push(program[i]);
            else
            {
                ll u = S.top();
                S.pop();
                ll v = S.top();
                S.pop();
                S.push(u + v);
            }
            return S.top();
        }

        int findMissing(vector <int> program, int wantedResult)
        {
            if (cal(program, 0) == wantedResult) return 0;
            ll u = cal(program, 1);
            if (u == wantedResult) return 1;
            ll v = cal(program, 2);
            if (u == v) return -1;
            if (u < wantedResult) return wantedResult - u + 1;
            else return -1;
        }
};

第二种方法:

/*29ms*/

typedef pair<ll, bool> p2;

stack<ll> s;
stack<p2> s2;
int n;

class Suminator
{
    public:
        int test0(vector<int> &p)
        {
            int i;
            ll x, y;
            For(i, n)
            {
                if (p[i] <= 0)
                {
                    if (!s.empty())
                    {
                        x = s.top(), s.pop();
                        if (!s.empty()) y = s.top(), s.pop(), s.push(x + y);
                        else s.push(x);
                    }
                }
                else s.push((ll)p[i]);
            }
            if (s.empty()) return -1;
            return s.top() > 1000000000LL ? 1000000001 : (int)s.top();
        }

        int test1(vector<int> &p)
        {
            int i;
            ll x, y;
            bool has1, has2;
            For(i, n)
            {
                if (p[i] == 0)
                {
                    if (!s2.empty())
                    {
                        x = s2.top().first, has1 = s2.top().second, s2.pop();
                        if (!s2.empty()) y = s2.top().first, has2 = s2.top().second, s2.pop(), s2.push(MP(x + y, has1 || has2));
                        else s2.push(MP(x, has1));
                    }
                }
                else if (p[i] == -1) s2.push(MP(1LL, true));
                else s2.push(MP((ll)p[i], false));
            }
            if (s2.empty() || !s2.top().second) return -1;
            return s2.top().first > 1000000000LL ? 1000000001 : (int)s2.top().first;
        }

        int findMissing(vector<int> p, int want)
        {
            n = p.size();
            if (test0(p) == want) return 0;
            int tmp = test1(p);
            return tmp == -1 || tmp > want ? -1 : 1 + want - tmp;
        }
};

Comments

comments powered by Disqus