头条笔试第三题错误答案--求大佬查错

第三题题目:

有N个参赛者围成一圈 (第0个人和第n - 1个人相邻),每个人有自己的参赛分数。现在给每人发奖品,要求:
(1)每人奖品个数起码为1;(2)如果一人的分数高于左右邻居,则其得到的奖品数目也要大于左右邻居。

输入第一个数M是一轮测试中会跑的例子总数;
第二个数N是共有多少个参赛者;
接下来N个数是这些参赛者的分数(按照参赛者围成一圈的顺序排列,第0个挨着第N - 1个)。要求输出最少的奖品数目之和。

我的代码:(case通过率为0,实在不知道问题出在哪里……不知道是输入输出的问题还是思路有错误,希望各位大佬指点……)


===============================更新============================
是我思路出错了……是我的边界条件处理得不够完整。

假设这N个人的分数是[3, 1, 6, 2, 1, 2, 8]
leftOrder表示,如果所有人只在意他左边的邻居在得分数目比他少的情况下,得奖数量比他少,那么最少每个人该有多少分?从左往右看,如下程序得到leftOrder是[1, 1, 2, 1, 1, 2, 3]
rightOrder表示,如果所有人只在意他右边的邻居在得分数目比他少的情况下,得奖数量比他少,那么最少每个人该有多少分?从右往左看,如下程序得到rightOrder是[2, 1, 2, 1, 1, 1, 2],但其实应该继续检查第0个数和第n - 1个数此时的得奖数量是否相等,如果相等,那么第n - 1个数还要继续 + 1,正确的rightOrder应该是[2, 1, 2, 1, 1, 2, 3], 也就是再加一个。

所以最后gift array应该是leftorder和rightOrder的每个元素分别取max,即是[2, 1, 2, 1, 1, 2, 3]。我自己测的例子都“巧妙”地避开了我程序的漏洞……唉心疼自己,只能凉凉了……

import java.util.Scanner;


public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int cycles = sc.nextInt();

for (int k = 0; k < cycles; k++) {

int n = sc.nextInt();

int[] scores = new int[n];

for (int i = 0; i < n; i++) {

scores[i] = sc.nextInt();

}

int[] leftOrder = new int[n];

int[] rightOrder = new int[n];

for (int i = 0; i < n; i++) {

if (i == 0) {

leftOrder[i] = scores[n - 1] < scores[i] ? 2 : 1;


continue;

}

leftOrder[i] = scores[i - 1] < scores[i] ? leftOrder[i - 1] + 1 : 1;


}

rightOrder[n - 1] = scores[n - 1] > scores[0] ? 2 : 1;

for (int i = n - 2; i >= 0; i--) {

rightOrder[i] = scores[i + 1] < scores[i] ? rightOrder[i + 1] + 1 : 1;

}

int sum = 0;

for (int i = 0; i < n; i++) {

sum += Math.max(leftOrder[i], rightOrder[i]);

}

System.out.print(sum);

}

}

}


#笔试题目##春招#
全部评论
** 老铁 我跟你一模一样 坐等大佬解释
点赞
送花
回复
分享
发布于 2019-03-16 12:20
问个问题。第二个例子。1 2 3 3 。为什么是8.第三个人和第四个人的分数比左右邻居高吗?不理解。
点赞
送花
回复
分享
发布于 2019-03-16 12:25
网易互娱
校招火热招聘中
官网直投
这道题我没看懂第二个1233的例子,🤣能讲一讲吗
点赞
送花
回复
分享
发布于 2019-03-16 12:25
是坐成一个环,不是一排
点赞
送花
回复
分享
发布于 2019-03-16 12:33
第三题的描述很奇怪,应该是对于pos=i的人来说,如果旁边的人比他分数高,那么拿的奖品应该比他多 如果score[left]>scrore[pos] 则gift[left] > gift[pos] 如果score[right]>scrore[pos] 则gift[right] > gift[pos] 也就是说拿多少奖全靠周围人的水平,向下取min
点赞
送花
回复
分享
发布于 2019-03-16 12:35
您举的例子里rightOrder结果不对吧 , 我觉得是 [2 1 3 2 1 1 2]
点赞
送花
回复
分享
发布于 2019-03-18 09:15

相关推荐

点赞 7 评论
分享
牛客网
牛客企业服务