保卫方案--京东OJ

来源：牛客网

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

示例

输入：

1 2 4 5 3

输出：

===================================================================

简单点说就是在一个环形链表中，AB两个数之间如果没有大于他们的数，那这两个数就构成一组通路，两个方向连通都可以。问这样的组合有几种？

看了网上各种解释，说下我的总结。

递减单调栈的做法

例子中的1 2 4 5 3

1.先创建一个vector<int>容器，依次放入

2.再创建一个栈，从vector最大数的位置开始放入栈中，先放入5，3和栈顶比较，3<5，3也放入。1也放入。到2时，2>1，count+1，1弹出，count+1（count就是最后的答案）。2再和栈顶数比较，2<3，2放入。4>2，count+1，2弹出，count+1。4>3，count+1，3弹出，count+1，4<5，4放入。

3.上面的各种进出栈什么意思呢？比如1这个数，就是找到左边最近比1大的数就是3，右边比1大的数就是2

4.count=6，栈中剩余的元素是5、4，又可以组合成一对，最后count=7。或者用2n-1也可以算出来，n就是剩下的数量，为什么是2n-1，我是多举个例子归纳出来的，里面数学原理没去多想

难点：如果有重复的数

比如输入

6 5 4 4 4 4

4个4排列组合4*3/2=6

5可以和每个4组合

6可以和每个4组合

5和6又可以组合

最后count=6+4+4+1=15

具体思路看代码

代码如下

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 struct node{
 7     int val;
 8     long count;
 9     node(int v, int c = 1): val(v), count(c){}
10 };
11 
12 int main() {
13     ios::sync_with_stdio(false);
14     int N;
15     while(cin >> N){
16         vector<int> watch(N);
17         for(int i = 0; i < N; ++i)
18             cin >> watch[i];
19 
20         vector<node> v;//不重复
21         node tmp(watch[0]);
22 
23         int max_h = watch[0];
24         int max_index = 0;
25         for(int i = 1; i < N; ++i){
26             if(watch[i] == watch[i - 1])
27                 tmp.count ++;
28             else{
29                 v.push_back(tmp);
30                 if( max_h < tmp.val){
31                     max_h = tmp.val;
32                     max_index = v.size() - 1;
33                 }
34                 tmp.val = watch[i];
35                 tmp.count = 1;
36             }
37         }
38         // 最后一个元素
39         v.push_back(tmp);
40         if( max_h < tmp.val){
41             max_h = tmp.val;
42             max_index = v.size() - 1;
43         }
44         int n = 0;
45         long count = 0;
46         vector<node> stack;
47         for(int i = max_index; n < v.size(); ++n, i = (i+1)%v.size()){
48             while( stack.size() && v[i].val > stack[stack.size() - 1].val){
49                 node & tmp = stack[stack.size() - 1];
50                 count += tmp.count + tmp.count*(tmp.count - 1)/2;//栈顶自我排列组合
51                 stack.pop_back();
52                 if(stack.size()) count += tmp.count;
53             }
54 
55             if( stack.size()){
56                 if(v[i].val == stack[stack.size() - 1].val)
57                     stack[stack.size() - 1].count += v[i].count;
58                 else
59                     stack.push_back(v[i]);
60             } else
61                 stack.push_back(v[i]);
62         }
63         while(stack.size()){
64             node & tmp = stack[stack.size() - 1];
65             count += tmp.count*(tmp.count - 1)/2;
66             stack.pop_back();
67             if(stack.size()) count += 2 * tmp.count;
68             if(stack.size()==1 &&stack[stack.size()-1].count==1) count-=tmp.count;
69         }
70         cout << count<<endl;
71     }
72     return 0;
73 }