1.題目描述
戰(zhàn)爭游戲的至關(guān)重要環(huán)節(jié)就要到來了峦树，這次的結(jié)果將決定王國的生死存亡橄仍，小B負(fù)責(zé)首都的防衛(wèi)工作。首都位于一個四面環(huán)山的盆地中，周圍的n個小山構(gòu)成一個環(huán)畴嘶，作為預(yù)警措施铭拧，小B計劃在每個小山上設(shè)置一個觀察哨像棘，日夜不停的瞭望周圍發(fā)生的情況咨察。 一旦發(fā)生外地入侵事件，山頂上的崗哨將點燃烽煙沛硅，若兩個崗哨所在的山峰之間沒有更高的山峰遮擋且兩者之間有相連通路眼刃，則崗哨可以觀察到另一個山峰上的烽煙是否點燃。由于小山處于環(huán)上摇肌，任意兩個小山之間存在兩個不同的連接通路擂红。滿足上述不遮擋的條件下，一座山峰上崗哨點燃的烽煙至少可以通過一條通路被另一端觀察到围小。對于任意相鄰的崗哨篮条，一端的崗哨一定可以發(fā)現(xiàn)一端點燃的烽煙。 小B設(shè)計的這種保衛(wèi)方案的一個重要特性是能夠觀測到對方烽煙的崗哨對的數(shù)量吩抓，她希望你能夠幫她解決這個問題。
2.輸入描述
輸入中有多組測試數(shù)據(jù)赴恨，每一組測試數(shù)據(jù)的第一行為一個整數(shù)n(3<=n<=106),為首都周圍的小山數(shù)量疹娶，第二行為n個整數(shù)，依次表示為小山的高度h（1<=h<=109）.
3.輸出描述
對每組測試數(shù)據(jù)伦连，在單獨的一行中輸出能相互觀察到的崗哨的對數(shù)雨饺。
4.示例
輸入
5
1 2 4 5 3
輸出
7
5.解題思路
這個題想了好長時間，但是一直沒想出來怎么做惑淳，參考了大神的解題思路后额港，總算想清楚了，原鏈接如下：http://www.cnblogs.com/mengmz/p/7263915.html歧焦。
分析題目可知移斩，對于山峰a,如果能在它的左邊和右邊分別找到最近且比它大的b和c，那么b能看到a，a能看到c向瓷，即整體計數(shù)對應(yīng)加2肠套。那么題目可以分為如下兩種情況進(jìn)行討論：
- 對于數(shù)組中無重復(fù)數(shù)字出現(xiàn)的情況，在構(gòu)成環(huán)的全部元素當(dāng)中猖任，最大值和次大值只有一邊存在比它大的數(shù)你稚，但能彼此看到，故計數(shù)值加1朱躺。除了這兩個元素外刁赖，剩下的n-2個元素都能在左邊和右邊分別找到比它大的數(shù)，故計數(shù)值加（n-1）*2长搀。即總的結(jié)果為：1+（n-2）*2宇弛。
- 對于有重復(fù)數(shù)字出現(xiàn)的情況，假設(shè)有一組序列為a,a,b,b,b,c,c且a>b,c>b盈滴。a,b,c分別出現(xiàn)的次數(shù)為2,3,2涯肩，b各元素能互相看見，故b自身能構(gòu)成的組合數(shù)為：c(3,2)=3*(3-1)/2巢钓。同時所有的b都能看到最后一個a和第一個c病苗，所以計數(shù)值加3+3。如果用N1,N2,N3分別表示a,b,c出現(xiàn)的話症汹，則總的結(jié)果為：c(N2,2)+2*N2;
分析完兩種情況后硫朦，現(xiàn)在我們需要求出每一個數(shù)和兩邊大于這個數(shù)的情況，采用單調(diào)棧來解決背镇，具體求解過程如下:
（1）讀取所有數(shù)據(jù)咬展，放入數(shù)組V，計數(shù)值count=0瞒斩。
（2）新建數(shù)組P破婆，遍歷數(shù)組V，將V中的元素消除重復(fù)后放入P中胸囱，并記錄下每個元素重復(fù)的次數(shù)祷舀。同時找出最大的元素max和其在P中下標(biāo)max_i。
-
（3）創(chuàng)建堆棧S烹笔，然后從max_i開始遍歷所有P中元素裳扯。進(jìn)行如下操作：
- 若堆棧為空， 將P[i]直接壓入堆棧谤职；
- 若堆棧為非空饰豺，將P[i]與棧頂元素進(jìn)行比較，如果大于棧頂元素允蜈，count加上棧頂元素的組合數(shù)（重復(fù)數(shù)N,組合數(shù)為c(N,2)+N,注意此時只考慮棧頂元素和P[i]的組合數(shù)）冤吨，然后彈出棧頂元素蒿柳，若棧不為空，則彈出的數(shù)和棧頂數(shù)也有組合數(shù)锅很，count加彈出數(shù)的重復(fù)數(shù)N其馏，執(zhí)行本步驟一直彈出直到P[i]小于棧頂元素；
- 若等于棧頂元素爆安，棧頂元素的重復(fù)數(shù)+P[i]的重復(fù)數(shù)叛复，繼續(xù)執(zhí)行；
- 若小于棧頂元素扔仓，直接壓入褐奥；
-
(4)上個步驟結(jié)束后，得到一個遞減的堆棧翘簇。依次彈出棧頂元素到temp撬码，直到堆棧為空，count加上其組合數(shù)目,這個時候要考慮以下情況：
- 堆棧中剩余元素個數(shù)多于1,則temp的組合數(shù)為c(N,2)+N*2版保。
- 堆棧中的剩余元素個數(shù)為1呜笑，若剩余元素的重復(fù)次數(shù)n大于1，則temp的組合數(shù)為c(N,2)+N
*2（如4,4,3,3,3序列）彻犁；若剩余的重復(fù)次數(shù)為1叫胁，則temp的組合數(shù)為c(N,2)+N（如4,3,3,3序列） - 堆棧中的剩余元素個數(shù)為0，此時temp為最大值汞幢，組合數(shù)跟其重復(fù)次數(shù)N有關(guān),為c(N,2)驼鹅；
6.實現(xiàn)代碼
#include<iostream>
#include <algorithm>
#include<vector>
#include<stack>
using namespace std;
//用結(jié)構(gòu)體來保存每個山峰的高度，和重復(fù)的次數(shù)
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;//去重和計數(shù)
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)//若重復(fù)
{
temp.count++;//計數(shù)
}
else
{
mnode.push_back(temp);
if(max<temp.val)//獲取最大峰值和對應(yīng)下標(biāo)
{
max=temp.val;
max_i=mnode.size()-1;//注意森篷，這里獲取的去重后的下標(biāo)
}
temp.val=mountin[i];
temp.count=1;
}
}
mnode.push_back(temp);
if(max<temp.val)//獲取最大峰值和對應(yīng)下標(biāo)
{
max=temp.val;
max_i=mnode.size()-1;//注意输钩，這里獲取的去重后的下標(biāo)
}
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)
{ //數(shù)組元素大于棧頂元素的情況
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;
}
//數(shù)組元素小于棧頂元素的情況
if(s.empty()||mnode[i].val<s.top().val) s.push(mnode[i]);
else //數(shù)組元素等于棧頂元素的情況
{
s.top().count+=mnode[i].count;
}
}
//對最后的遞減棧進(jìn)行求解
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.思考與分析
- 解題的時候還是需要學(xué)會將大問題化解之后進(jìn)行分析，分情況不斷討論岩馍，然后也就能分而解之，水到渠成抖韩。
