专栏首页mathor保卫方案(京东笔试题)

保卫方案(京东笔试题)

Question

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

输入描述

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

输出描述

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

思路

 你要说这是单调栈板子题似乎有点看不起京东。总结一下,两座山A,B之间能通信的要求是,A,B之间的点都比这个点小,确实看到这很容易想到单调栈,构建一个单调递减栈,以1,2,4,5,3为例。  首先找到这些元素中的最大值,以最大值作为起点进行入栈操作,那么5,3,1依次入栈,接下来要入栈的是2,2大于1,所以1出栈,1的左边(3),右边(2)。那么1是可以看到2和3的,有两对。res += 2  4准备进栈,4大于2,所以2要出栈,2的左边(3),右边(4),res += 2。  同理,3也要出栈,res += 2。此时栈里面只有4和5作为一对,res += 1。  上述是一种特殊情况,没有重复元素时,如果有重复元素,假设数组是4,4,5,5,6,6,此时stack中存的是一个pair,pair中包含两个变量,当前存的值,以及该值的个数,比方说遍历数组,首先是下标为4的6先进栈,然后下标为5的6进栈,因为值相同,所以pair.times++,然后两个4进栈,此时的情况见下图

 4要出栈,但是此时res要加多少呢?这其实是一个排列组合的问题res += C(4,2)+2*2,然后两个5都进来了,数组遍历结束,但是此时栈中还有值

 数组遍历完了,但是栈中还有值,这种情况要特殊讨论

  • 栈中元素个数大于2,res += C(stack.peek().times,2) + 2*stack.pop().times
  • 栈中元素个数等于2
    • 如果栈底元素的times==1,则res += C(stack.peek().times,2)+stack.pop().times
    • 如果栈底元素的times !=1 ,则res += C(stack.peek().times,2)+2*stack.pop().times
  • 栈中元素小于2(就一个),res += C(stack.pop().times,2)

代码

package nowcoder;
import java.util.*;
public class Main {
    public static int nexIndex(int size,int i) {
        return i < (size - 1) ? (i + 1) : 0;
    }
    private static class Pair {
        public int value;
        public int times;
        Pair(int value) {
            this.value = value;
            this.times = 1;
        }
    }
    public static long getInternalSum(int k) {
        return k == 1L ? 0L : (long)k * (long)(k - 1) / 2L;
    }
    public static long communications(int[] arr) {
        if(arr == null || arr.length < 2)
            return 0;
        int size = arr.length;
        int maxIndex = 0;
        for(int i = 0;i < size;i++)
            maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
        int value = arr[maxIndex];//最大值
        int index = nexIndex(size,maxIndex);//最大值的下一个
        long res = 0L;
        Stack<Pair> stack = new Stack<Pair>();
        stack.push(new Pair(value));
        while(index != maxIndex) {
            value = arr[index];
            while(!stack.isEmpty() && stack.peek().value < value) {
                int times = stack.pop().times;
                res += getInternalSum(times) + 2 * times;//C(times,2) + 2 * times
            }
            if(!stack.isEmpty() && stack.peek().value == value) 
                stack.peek().times++;
            else 
                stack.push(new Pair(value));
            index = nexIndex(size,index);
        }
        while(!stack.isEmpty()) {
            int times = stack.pop().times;
            res += getInternalSum(times);
            if(!stack.isEmpty()) {
                res += times;
                if(stack.size() > 1)
                    res += times;
                else 
                    res += stack.peek().times > 1 ? times : 0;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int n = cin.nextInt();
            int[] arr = new int[n];
            HashSet<Integer> tmp = new HashSet<Integer>();
            for(int i = 0;i < n;i++) {
                arr[i] = cin.nextInt();
                tmp.add(arr[i]);
            }
            if(tmp.size() == n)//没有重复元素,直接用结论
                System.out.println((long)2 * n - 3);
            else
                System.out.println(communications(arr));
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CodeForces E. XOR and Favorite Number(Div.2)

     一个莫队的基础题,题目要求[L,R]里面有多少对子区间异或值为k,记录一下前缀异或和arr,因为x^x=0,现在我们要求区间[L,R]的异或和值,用arr...

    mathor
  • CodeForces D.Powerful array(Div.1)

     大意是是说,问区间[L,R]内的的一个值,这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle,...

    mathor
  • HDOJ1257最少拦截系统

     这个题一开始我百思不得其解,后来看了一眼别人的题解标题,最长上升子序列?我当时还纳闷,这和最长上升子序列有什么关系,后来仔细一想还确实是。因为导弹拦截系统...

    mathor
  • 简单的验证码识别(opecv)

           opencv版本: 3.0.0            处理验证码: 纯数字验证码 (颜色不同,有噪音,和带有较多的划痕)             ...

    Gxjun
  • 最长递减子序列(nlogn)(个人模版)

    最长递减子序列(nlogn): 1 int find(int n,int key) 2 { 3 int left=0; 4 int ri...

    Angel_Kitty
  • 三行代码接入,社交软件打字时底下弹出的表情布局,自定义ViewPager+页面点标+各种功能的android小框架。

    (转载请声明出处:https://cloud.tencent.com/developer/user/1148436/activities) 前言:       ...

    林冠宏-指尖下的幽灵
  • P1001 A+B Problem

    两个整数以空格分开 输出格式: 一个数 输入输出样例 输入样例#1: 复制 20 30 输出样例#1: 复制 50

    瑞新
  • 超像素经典算法SLIC的代码的深度优化和分析。

         现在这个社会发展的太快,到处都充斥着各种各样的资源,各种开源的平台,如github,codeproject,pudn等等,加上一些大型的官方的开源软件...

    用户1138785
  • 背包九讲-问法的灵活变化

    要求的是“总价值最小”“总件数最小”,只需简单的将上面的状态转移方程中的max改成min即可。

    十四君
  • P2661 信息传递

    题目描述 有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学。 游戏...

    attack

扫码关注云+社区

领取腾讯云代金券