顺丰科技的笔试题-浴室歌手
发布于 2017-09-23 16:58 2958 次浏览 0 赞 来自 笔试面试  

最后结果10%,然而刚结束,我就想到了问题所在,然后加个if判断,就解决问题了。让我哭一会

9 条回复

有没有大佬,贴上自己的代码,观摩一下啊

2017-09-23 16:59

import java.util.Scanner;


public class SingerMain {


public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int m = sc.nextInt();

int[] a = new int[n];

int[] aa = new int[m];


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

aa[i] = sc.nextInt();

}


for (int j = 0; j < m; j++) {

a[aa[j] - 1] = 1;

}

double[] len = new double[n];

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

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

if (a[j] == 1) {

len[i] += Math.abs(j - i);

}

}

}

double min = n;

int index = 0;


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

if (len[k] / m > 1.0) {

if (a[k] != 1) {

if (len[k] / m < min) {

index = k + 1;

min = Math.min(min, len[k] / m);

}

}

}

}

System.out.println(index);


}


}

贴上自己的代码

2017-09-23 17:01

说下思路吧?

我也是10%,想不通错在哪儿

2017-09-23 17:18
coder_zLKNWibX 回复 coder_WCX8DKPY

我采用的是枚举法,就是计算每个空的位置到所有有人的位置的和,求这些和的最小值,然后输出坐标即可

2017-09-23 17:57
coder_VJ58GR3G 回复 coder_zLKNWibX

你这样做不超时吗?

2017-09-23 18:49

说一下我的思路。

创建一个n长度的数组表示浴室位置,被占的为1,空位为0。

从1号遍历所有为0 的位置,计算与被占的位置的距离和,输出最小位置即可。

但是这样做法时间复杂度为n^2.

只会完成30%。超时

这时候就需要优化了。

我们可以考虑一下,最近位置只最远可能是为第一个为1的左边一位,和最后一个为1的右边一位。

所以在遍历计算距离的时候,从第一个为1的左边一位到最后一个为1的右边一位。

时间刚刚够。就AC了

2017-09-23 18:56
1
coder_zLKNWibX 回复 coder_VJ58GR3G

嗯嗯,我的思路就是你说的前面这个,时间复杂度为n^2,你的这个想法很好

2017-09-24 00:20
coder_zLKNWibX 回复 coder_VJ58GR3G

如果不计算Scanner的输入时间,我测试了,不会超时的

2017-09-24 01:05

第一题求贴代码。

2017-10-04 17:17
添加回复
回到顶部