当前位置: 代码迷 >> 综合 >> 2018 蓝桥杯省赛 B 组模拟赛(五) G. 程序设计:合并数字
  详细解决方案

2018 蓝桥杯省赛 B 组模拟赛(五) G. 程序设计:合并数字

热度:41   发布时间:2023-11-20 06:10:30.0

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

输入格式

输入第一行为一个整数 n(1<=n <=10^5)n(1n105),表示数字的总数

第二行为 n 个整数 x_1,x_2,...,x_n(0 <=xi?<=10^9)x1?,x2?,...,xn?(0xi?109),表示这些数。

输出格式

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

样例输入

4
1 2 0 1

样例输出

3

#include<iostream>
#include<stack>
using namespace std;
stack<int>s;
int main()
{int n,x,ans=0;cin>>n;cin>>x;s.push(x);for(int i=1;i<n;i++){cin>>x;while(!s.empty()&&s.top()-x==1){s.pop();ans++;}if(!s.empty()&&x-s.top()==1){ans++;}else{s.push(x);}}cout<<ans;
}

  相关解决方案