The website uses cookies. By using this site, you agree to our use of cookies as described in the Privacy Policy.
I Agree

搜狐笔试题-发奖金

dancheren 2017-07-31 20:04:58 791

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

输入描述:
每组数据先输入N,然后N行输入N个正整数,每个数表示每个组的比赛成绩。
输出描述:
输出至少需要多少w的奖金
示例1

输入

10
20 
32 
12 
32 
45 
11 
21 
31 
41 
33

输出

20

解题思路:此题的要求是每个队可以看见他相邻的队的低于自己的成绩,在此情况下,他的奖金应该要多于成绩低的那个对的奖金。我们可以比较当前队与后一个队的成绩,如果当前队伍的成绩高于后一个队,那么当前队伍的奖金至少应该是后一个队的奖金加上1,然后再反向遍历当前队伍的前一个结点,如果前一个队伍成绩高于当前结点,并且前一个队伍的奖金比当前队伍的奖金加上1要少,那么更新前一个队伍的奖金为当前队伍的奖金加上1,如果前一个队伍的成绩低于当前队伍,不更新。如果两个队伍成绩一样,将当前队伍的奖金更新到前一个队伍。继续向前遍历,直到第一个队伍。如果当前结点的成绩低于后一个队伍的成绩,二后一个队伍的奖金少于当前队伍奖金加1,则更新后一个队伍的奖金为当前队伍奖金加1;如果当前队伍的成绩与后一个队伍的成绩相等,则将当前队伍的奖金更新到后一个队伍。将当前队伍右移一次到下一个队伍。直到最后一个队伍。

此种方法主要思路就是每更新一个队伍,都需要反向去更新它之前的队伍,这个思想很重要。下面是代码:

  1. import java.util.Scanner;
  2. public class Main{
  3. public static void main(String[] args) {
  4. Scanner sc = new Scanner(System.in);
  5. while (sc.hasNext()) {
  6. int n = sc.nextInt();
  7. int[] ints = new int[n];
  8. int[] copy = new int[n];
  9. for (int i = 0; i < n; i++) {
  10. copy[i] = 1;
  11. }
  12. for (int i = 0; i < n; i++) {
  13. ints[i] = sc.nextInt();
  14. }
  15. for (int i = 0; i < n - 1; i++) {
  16. if (ints[i] > ints[i + 1]) { //当前队伍成绩高于后一个队伍
  17. if (copy[i] < copy[i + 1] + 1) {
  18. copy[i] = copy[i + 1] + 1; //更新当前队伍的奖金
  19. }
  20. for (int j = i; j > 0; j--) { //反向更新前面队伍的奖金
  21. if (ints[j] < ints[j - 1]) { //前一个队伍的成绩高于当前队伍的成绩
  22. if (copy[j - 1] < copy[j] + 1) {
  23. copy[j - 1] = copy[j] + 1;
  24. }
  25. } else if (ints[j] > ints[j - 1]) { //前一个队伍的成绩低于当前队伍的成绩
  26. if (copy[j] < copy[j - 1] + 1) {
  27. copy[j] = copy[j - 1] + 1;
  28. }
  29. } else { //前一个队伍的成绩等于当前队伍的成绩
  30. copy[j - 1] = copy[j];
  31. }
  32. }
  33. } else if (ints[i] < ints[i + 1]) { //当前队伍的成绩低于后一个队伍的成绩
  34. if (copy[i + 1] < copy[i] + 1) {
  35. copy[i + 1] = copy[i] + 1;
  36. }
  37. } else { //当前队伍的成绩等于后一个队伍的成绩
  38. copy[i + 1] = copy[i];
  39. }
  40. }
  41. int result = 0;
  42. for (int i = 0; i < n; i++) {
  43. result += copy[i];
  44. }
  45. System.out.println(result);
  46. }
  47. }
  48. }


Measure
Measure
Summary | 1 Annotation
他的奖金应该要多于成绩低的那个对的奖金
2021/04/08 04:29