1.保卫方案 | 野渡的博客

战争游戏的至关重要环节就要到来了，这次的结果将决定王国的生死存亡，小B负责首都的防卫工作。首都位于一个四面环山的盆地中，周围的n个小山构成一个环，作为预警措施，小B计划在每个小山上设置一个观察哨，日夜不停的瞭望周围发生的情况。一旦发生外地入侵事件，山顶上的岗哨将点燃烽烟，若两个岗哨所在的山峰之间没有更高的山峰遮挡且两者之间有相连通路，则岗哨可以观察到另一个山峰上的烽烟是否点燃。由于小山处于环上，任意两个小山之间存在两个不同的连接通路。满足上述不遮挡的条件下，一座山峰上岗哨点燃的烽烟至少可以通过一条通路被另一端观察到。对于任意相邻的岗哨，一端的岗哨一定可以发现一端点燃的烽烟。小B设计的这种保卫方案的一个重要特性是能够观测到对方烽烟的岗哨对的数量，她希望你能够帮她解决这个问题。

保卫方案

题目原链接：https://www.nowcoder.com/practice/e1967ae812ea42e7a3ce57ee1f83b686?tpId=85&tqId=29878&rp=2&ru=/activity/oj&qru=/ta/2017test/question-ranking

1.题目描述

2.输入描述

输入中有多组测试数据，每一组测试数据的第一行为一个整数n(3<=n<=10^6),为首都周围的小山数量，第二行为n个整数，依次表示为小山的高度h（1<=h<=10^9）.

3.输出描述

对每组测试数据，在单独的一行中输出能相互观察到的岗哨的对数。

4.示例

输入

1 2	5 1 2 4 5 3

输出

5.解题思路

这个题想了好长时间，但是一直没想出来怎么做，参考了大神的解体思路后，总算想清楚了，原链接如下：http://www.cnblogs.com/mengmz/p/7263915.html。

分析题目可知，对于山峰a,如果能在它的左边和右边分别找到最近且比它大的b和c，那么b能看到a，a能看到c，即整体计数对应加2。那么题目可以分为如下两种情况进行讨论：

对于数组中无重复数字出现的情况，在构成环的全部元素当中，最大值和次大值只有一边存在比它大的数，但能彼此看到，故计数值加1。除了这两个元素外，剩下的n-2个元素都能在左边和右边分别找到比它大的数，故计数值加（n-1）2。即总的结果为：1+（n-2）2。
对于有重复数字出现的情况，假设有一组序列为a,a,b,b,b,c,c且a>b,c>b。a,b,c分别出现的次数为2,3,2，b各元素能互相看见，故b自身能构成的组合数为：c(3,2)=3(3-2)/2。同时所有的b都能看到最后一个a和第一个c，所以计数值加3+3。如果用N1,N2,N3分别表示a,b,c出现的话，则总的结果为：c(N2,2)+2N2;

分析完两种情况后，现在我们需要求出每一个数和两边大于这个数的情况，采用单调栈来解决，具体求解过程如下:

（1）读取所有数据，放入数组V，计数值count=0。
（2）新建数组P，遍历数组V，将V中的元素消除重复后放入P中，并记录下每个元素重复的次数。同时找出最大的元素max和其在P中下标max_i。
（3）创建堆栈S，然后从max_i开始遍历所有P中元素。进行如下操作：
- 若堆栈为空，将P[i]直接压入堆栈；
- 若堆栈为非空，将P[i]与栈顶元素进行比较，如果大于栈顶元素，count加上栈顶元素的组合数（重复数N,组合数为c(N,2)+N,注意此时只考虑栈顶元素和P[i]的组合数），然后弹出栈顶元素，若栈不为空，则弹出的数和栈顶数也有组合数，count加弹出数的重复数N，执行本步骤一直弹出直到P[i]小于栈顶元素；
- 若等于栈顶元素，栈顶元素的重复数+P[i]的重复数，继续执行；
- 若小于栈顶元素，直接压入；
(4)上个步骤结束后，得到一个递减的堆栈。依次弹出栈顶元素到temp，直到堆栈为空，count加上其组合数目,这个时候要考虑以下情况：
- 堆栈中剩余元素个数多于1,则temp的组合数为c(N,2)+N*2。
- 堆栈中的剩余元素个数为1，若剩余元素的重复次数n大于1，则temp的组合数为c(N,2)+N*2（如4,4,3,3,3序列，所有的3能看到第一个4和最后一个4）；若剩余的重复次数为1，则temp的组合数为c(N,2)+N（如4,3,3,3序列）
- 堆栈中的剩余元素个数为0，此时temp为最大值，组合数跟其重复次数N有关,为c(N,2)；

6.实现代码

#include<iostream>
#include <algorithm>
#include<vector>
#include<stack>
using namespace std;

//用结构体来保存每个山峰的高度，和重复的次数
struct node{
    int val;
    long count;
    node(int v,int c=1): val(v),count(c){};
};

int main()
{
    int n,value,i,max,max_i;
    long count=0;

    cin>>n;
    
    vector<int> mountin(n);
    vector<node> mnode;//去重和计数
    for(i=0;i<n;i++)
    {
        cin>>mountin[i];//依次获取每个山峰的值
    }
    
    node temp(mountin[0]);
    max=mountin[0];
    for(i=1;i<n;i++)//去重和寻找最大值
    {
        if(mountin[i]==temp.val)//若重复
        {
            temp.count++;//计数
        }
        else  
        {
            mnode.push_back(temp);
            if(max<temp.val)//获取最大峰值和对应下标
            {
                max=temp.val;
                max_i=mnode.size()-1;//注意，这里获取的去重后的下标
            }
            temp.val=mountin[i];
            temp.count=1;
        }
    }
    
    mnode.push_back(temp);
    if(max<temp.val)//获取最大峰值和对应下标
    {
        max=temp.val;
        max_i=mnode.size()-1;//注意，这里获取的去重后的下标
    }
    
    stack<node> s;
    n=0;
    for(i=max_i;n<mnode.size();++n,i=(i+1)%mnode.size())
    {
        while(!s.empty() && mnode[i].val>s.top().val)
        {   //数组元素大于栈顶元素的情况
            temp.val=s.top().val;
            temp.count=s.top().count;
            count+=temp.count*(temp.count-1)/2+temp.count;
            s.pop();
            if(!s.empty()) count+=temp.count;
        }
        //数组元素小于栈顶元素的情况
        if(s.empty()||mnode[i].val<s.top().val) s.push(mnode[i]);
        else //数组元素等于栈顶元素的情况
        {
            s.top().count+=mnode[i].count;
        }
    }
    
    //对最后的递减栈进行求解
    while(!s.empty())
    {
        temp.val=s.top().val;
        temp.count=s.top().count;
        s.pop();
        if(s.size()>1)  count+=temp.count*(temp.count-1)/2+2*temp.count;
        else if(s.size()==0) count+=temp.count*(temp.count-1)/2;
        else //堆栈中还剩一个值的情况
        {   
            if(s.top().count==1) //如4，3，3，3
            {
                count+=temp.count*(temp.count-1)/2+temp.count;
            }
            else //如4,4，3，3，3
            {
                count+=temp.count*(temp.count-1)/2+2*temp.count;
            }
        }
        
    }
    cout<<count<<endl;
    return 0;
}

6.思考与分析

解题的时候还是需要学会将大问题化解之后进行分析，分情况不断讨论，然后也就能分而解之，水到渠成。