京东编程真题_牛客_JD6——保卫方案

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

1 2 4 5 3

输出

思路

左程云老师单调栈的思路才是正解，牛客其它面向数据编程的都是“耍流氓”🤦♂️。

if (n >= 1000000) {
    cout << 499999500000 << endl;
    return 0;
}

在看题解之前我都没想到1ms能过这道题。
这道题如果山峰的高度各异，则答案为2*n-3。

题解

#include <iostream>
#include <vector>

#define choose(a,b,c) c=="max"?(a>b?a:b):(a>b?b:a)
#define ll long long
using namespace std;

vector<int> getMaxIndex(int a[],int s,int e){
    vector<int> arr;
    int max = s+1;
    arr.push_back(max);
    for(int i=s+2;i<e;i++){
        if(a[max]<a[i]){
            arr.clear();
            arr.push_back(i);
            max = i;
        } else if(a[max]==a[i]){
            arr.push_back(i);
        }
    }
    return arr;
}


ll count(int a[],int s,int e){
    if(e-s==1)return 0;
    vector<int> arr = getMaxIndex(a,s,e);
    long c = (int)arr.size();
    int f = arr[0];
    int l = arr.back();
    long r1 = count(a,s,f)+c;
    long r2 = count(a,l,e)+c;
    long sum1= c*(c-1)/2;
    for(int i=1;i<arr.size();i++){
        sum1 += count(a,arr[i-1],arr[i]);
    }
    return r1+r2+sum1;
}

int main(){
    int n;
    cin>>n;
    int *m = (int *)malloc(sizeof(int)*n*2);
    for(int i=0;i<n;i++) cin>>m[i];
    for(int i=n;i<2*n;i++) m[i] = m[i-n];
    int maxFirst = 0, maxSecond = 1;
    for(int i=1;i<n;i++){
        if(m[i]>m[maxFirst]){
            maxSecond = maxFirst;
            maxFirst = i;
        } else if(m[i]>m[maxSecond]){
            maxSecond = i;
        }
    }
    int start = choose(maxFirst, maxSecond, "min");
    int mid = choose(maxFirst, maxSecond, "max");
    int end = start + n;
    ll ans = count(m,start,mid) + count(m,mid,end) + 1;
    cout<<ans;
    return 0;
}

京东编程真题_牛客_JD6——保卫方案