计蒜客2018省赛B组模拟五《G合并数字》

本文主要是介绍计蒜客2018省赛B组模拟五《G合并数字》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蒜头君得到了 $n$ 个数，他想对这些数进行下面这样的操作，选出最左边的相邻的差的绝对值为 $1$ 的两个数，只保留较小的数，删去较大的数，直到没有两个相邻的差的绝对值为 $1$ 的数，问最多可以进行多少次这样的操作？

输入格式

输入第一行为一个整数 $\leq n \leq 10^5)$ ，表示数字的总数

第二行为 $n$ 个整数 $x_1,x_2,...,x_n(0 \leq x_i \leq 10^9)$ ，表示这些数。

输出格式

输出一行，为一个整数，表示蒜头君最多可以进行多少次这样的操作。

样例输入

4
1 2 0 1

样例输出

解题思路：利用STL stack来求解

代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    stack<int>s;
    int a[100005];
    int i,n,ans = 0;
    cin>>n;
    for(int i = 0;i < n;i++)
    {
        cin>>a[i];
    }
    s.push(a[0]);
    i = 1;
    while(i<n)
    {
        if(fabs(s.top()-a[i])==1)
        {
            ans++;
            if(s.top()>a[i])
            {
                if(s.size()>1)
                {
                    s.pop();
                }
                else
                {
                    s.pop();
                    s.push(a[i]);
                    i++;
                }
            }
            else
            {
                i++;
            }

}
        else
        {
            s.push(a[i]);
            i++;
        }
    }
    while(s.size())
    {
        s.pop();
    }
    cout<<ans<<endl;
}

这篇关于计蒜客2018省赛B组模拟五《G合并数字》的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！