题目描述

狐进行了一次黑客马拉松大赛,全公司一共分为了N个组,每组一个房间排成一排开始比赛,比赛结束后没有公布成绩,但是每个组能够看到自己相邻的两个组里比自己成绩低的组的成绩,比赛结束之后要发奖金,以1w为单位,每个组都至少会发1w的奖金,另外,如果一个组发现自己的奖金没有高于比自己成绩低的组发的奖金,就会不满意,作为比赛的组织方,根据成绩计算出至少需要发多少奖金才能让所有的组满意。
输入描述:

每组数据先输入N,然后N行输入N个正整数,每个数表示每个组的比赛成绩。

输出描述:

输出至少需要多少w的奖金

输入例子:

10
20
32
12
32
45
11
21
31
41
33

输出例子:

20

2 收藏


直接登录
最新评论
  • freemind   05/23

    找发1w的就行了

    a0=9999

    a1开始存储

    n=1开始比较

    a[n]<a[n-1]且a[n]<a[n+1],这人就发1w,

    然后按1w分段,向右就加+1到该段结束。

    最后看看a1发了1w还是发2w

    10 20 30 12 32 45 11 21 31 41 33

    1              1             1                 1

    99 10 32 12 52 05 11 21 31 11 13

    1         1        1                  1

     

    99分和13分发一样多。找谁说理去

     

    • angelfish   05/23

      题干中“每个组能够看到自己相邻的两个组里比自己成绩低的组的成绩”,你有考虑“左中右”三个人的成绩一样,中间的人什么都看不到的情况吗?还有所有人成绩都一样,谁都不知道其他人成绩的情况吗?

       

      发放原则分析:

      ——————————————————————————

      设有三个组:a[i-1],a[i],a[i+1],

      相应的发放金额为:v[i-1],v[i],v[i+1],

      其中:v[i]未知,v[i-1]和v[i+1]可能未知也可能已经计算好。

       

      如果:a[i] 不能看到 a[i-1] 和a[i+1]的成绩,给a[i]发放v[i]=1

      如果:a[i] 只能看到 a[i-1] 的成绩,且a[i-1]已经算好发放的金额v[i-1],给a[i]发放v[i] = v[i-1] + 1

      如果:a[i] 只能看到 a[i+1] 的成绩,且a[i+1]已经算好发放的金额v[i+1],给a[i]发放v[i] = v[i+1] + 1

      如果:a[i] 能看到a[i-1]和 a[i+1] 的成绩,且a[i-1]和a[i+1]已经算好发放的金额v[i-1]和v[i+1],给a[i]发放v[i] = max(v[i-1],v[i+1]) + 1

       

      需要从左到右扫描N个组多次,知道计算好所有的v[1],v[2],。。。v[N]

      ——————————————————————————

       

      输入数据分析:

      ——————————————————————————

      第1轮:

      20 – 30 – 12 – 32 – 45 – 11 – 21 – 31 – 41 – 33

      [20:1] – 30 – [12:1] – 32 – 45 – [11:1] – 21 – 31 – 41 – [33:1]

      发放:1万 + 1万 + 1万 + 1万= 4 万

       

      ——————————————————————————

      第2轮:

      [20:1] – [30:2] – [12:1] – [32:2] – 45 – [11:1] – [21:2] – [31:3] – 41 – [33:1]

      发放:2万 + 2万 + 2万 + 3万= 9 万

       

      ——————————————————————————

       

      第3轮:

      [20:1] – [30:2] – [12:1] – [32:2] – [45:3] – [11:1] – [21:2] – [31:3] – [41:4] – [33:1]

      发放:3万 + 3万= 7 万

      ——————————————————————————

      一共发放:4万 + 9万 +7万 = 20万

      • freemind   05/23

        没考虑同样分数情况

        你的解答也有问题,11个人你就发了10份钱,还发了20w.

         

        • angelfish   05/24

          大哥你自己审题好不。。。

          输入示例中,是有11个数字,但是第一个数字10是指示接下来有10个数字

          (

          20
          32
          12
          32
          45
          11
          21
          31
          41
          33

          ),

          每个数字表示一个组的成绩。

           

          输出示例中的20,就是答案20万。

           

          我的解法自信是没有问题的^_^

        • angelfish   05/24

          另外,如果有N个组,所有组的分数都相同,那么任何一组都看不到其他组的成绩,给所有组都发1万就行了,那么答案就是N万。

           

          这种所有人成绩相同的情况,如果通过我上文指出的发放原则分析,对应:

          ——————————————————————————

          如果:a[i] 不能看到 a[i-1] 和a[i+1]的成绩,给a[i]发放v[i]=1;

          ——————————————————————————

          因此从左到右扫描一次,就能算出每个组应该发放的金额,既每组都是1万。

           

  • hido   05/25

    • angelfish   05/25

      哥们,你这答案明显不对啊。。。给你的如下例子:

      输入例子:

      3
      10
      20
      10

      输出例子:

      4

      你的程序输出是5哦。。。应该你给3个组分别发了 1,3,1,其实只要 1,2,1 就可以了

      • hido   05/25

        多谢指出,的确是审题除了问题,已修改:

         

        • angelfish   05/26

          算法是没问题了,但是效率有待改进哦!

          这for 循环要执行 n 次,第 i 次最坏情况要比较 n-i 次,复杂度  O(n^2)。这里的最坏情况就是倒序排列的,比如:5 4 3 2 1

           

          你可以做个预处理。

          从右到左扫描,对第 i 个数a[i],计算对应的less[i],表示a[i]的右边有多少个连续比a[i]小的。其中:

          less[i] = a[i] > a[i+1] ? less[i] = less[i+1] + 1 : 0

          只要遍历一次就行了,效率能提高很多哦!

           

          • hido   05/26

            哈哈,多谢大神指点,等会马上去试试。

            • angelfish   05/26

              帮你改了一下,你参考下。不怎么会写JavaScript,见笑了,哈哈

              • hido   05/26

                多谢,我算法这块一直比较弱,对我非常有帮助,哈哈。

                • angelfish   05/26

                  另一种思路,直接对a[i]计算处理左边连续比它小的元素个数,和右边连续比它小的元素个数,然后取两者最大值,再加一,就是应该发给a[i]的奖金了。只要遍历数组 3 次。

  • bo   05/27