网易笔试（网易笔试到底有多难）

　　网易笔试（网易笔试到底有多难）
　　作者：帅地
　　来源：苦逼的码农
　　今天我要将的这道题是网易 8 月 3 号研发岗笔试的第一题，也是四道题中最简单的一道。这道题涉及到前缀和的应用，所以我想借这道题给大家讲一讲前缀和相关的一些知识，以后大家遇到这道题，就可以快速秒杀了。
　　问题描述
　　下面我描述下这道题，不过我给的描述是简化版的，实际上再做笔试题的时候，每道题的描述都巨长，一般都会根据实际场景来给出问题的，有些人可能阅读了十几分钟，然后不知道自己要干嘛，我这里给出最简化的版本。有一个班级有 n 个人，给出 n 个元素，第 i 个元素代表 第 i 位同学的考试成绩，接下来进行 m 次询问，每次询问给出一个数值 t ，表示第 t 个同学，然后需要我们输出第 t 个同学的成绩超过班级百分之几的人，百分数 p 可以这样算：p = (不超过第 t 个同学分数的人数 ) / n * 100%。输出的时候保留到小数点后 6 位，并且需要四舍五入。输入描述：第一行输入两个数 n 和 m，两个数以空格隔开，表示 n 个同学和 m 次询问。第二行输入 n 个数值 ni，表示每个同学的分数，第三行输入 m 个数值mi，表示每次询问是询问第几个同学。（注意，这里 2<=n，m<=100000，0<=ni<=150，1<=mi<=n）输出描述：输出 m 行，每一行输出一个百分数 p，代表超过班级百分之几的人。示例1：输入 ：3 250 60 701 2输出33.333333%66.666667%
　　第一题大致是这样，不过不是和原题完全一样哈，在输入和输出有小许区别，因为具体的输入输出我忘了。我这个描述说简化好像也挺长，不过原题就更加长了。
　　解答
　　那么这道题难吗？说实话不难，不过你可以先自己再脑子里想想怎么做比较好，或许在考场上 20 分钟你还真不一定做的出来。
　　有些人说，这还不简单，每次询问的时候，我都遍历一下所有人的成绩，这样的花时间复杂度是 O(n * m)，显然，如果你这样做，那么是一定通不过的，一定会超时。一般暴力法能够通过 20% ~ 30% 的测试用力，如果一道题 20 分的话，能拿到 4~6 分。如果你实在没思路，那么暴力也是个不错的选择。
　　1、二分法
　　这道题我是用二分法做的，就是先对所有人的成绩进行排序，不过排序的时候我们需要开一个新的数组来存储。然后每次查询的时候可以通过二分查找进行匹配，由于用到了排序，需要花 O(nlogn) 的时间，m 次查询花的时间大致为 O(mlogn)。所以平均时间复杂度可以算是 O((m+n)logn)。这个时间复杂度通过所有测试用例，代码如下(没学过java的也能看懂)：publicclassMain{  //主函数，相当于c语言的main方法  publicstaticvoidmain(String[]args){  Scannerin=newScanner(System.in);  intm=in.nextInt();  intn=in.nextInt();  //存放成绩的数组  int[]a=newint[n];  //存放排序过后的成绩  int[]b=newint[n];  //输入n个人的成绩  for(inti=0;i<n;i++){  a[i]=in.nextInt();  b[i]=a[i];  }  //排序  Arrays.sort(b);  //进行查询  for(intj=0;j<m;j++){  //输入是要查询第几个同学  intt=in.nextInt();  //把这个同学的分数拿出来  intfen=a[t-1];  //通过二分查找是排在第几位  intsum=binarySearch(b,fen)-1;  doublet=sum*1.0/n*100;  System.out.printf(＂%.6f\n＂,t);  }  }  privatestaticintbinarySearch(int[]b,intfen){  intl=0;  intr=b.length-1;  while(l<=r){  intmid=l+(r-l)/2;  if(b[mid]>fen){  r--;  }elseif(b[mid]<fen){  l++;  }else{  //由于存在分数相同的人，所以还要往后查找  while(mid<b.length&&b[mid]==fen){  mid++;  }  returnmid;  }  }  return0;  }  }这里说明一下，输出的时候我没有输出＂%＂号哈。
　　前缀和
　　不过这道题更好的做法是采用前缀和来做。题设中每个同学的分数不超过 150，不小于 0，那么我们可以用一个数组 arr，然后让 arr[i] 表示分数不超过 i 的人数。通过这种方式，我们可以把时间复杂度控制在 O(n+m)。直接看代码吧，会更好理解（这里我就不写输入的代码了，用a[]存放成绩，m[]存放m次询问）：voidf(inta[],intm[]){  intn=a.length;  int[]arr=newint[151];  //先统计分数为i的有多少人  for(inti=0;i<n;i++){  arr[a[i]]++;  }  //接着构造前缀和  for(inti=1;i<151;i++){  arr[i]=arr[i]+arr[i-1];  }  //进行m次询问  for(inti=0;i<m.length;i++){  //取出成绩  intscore=a[m[i]-1];  //有多少人的成绩不超过score的  intsum=arr[score];  System.out.printf(＂%.6f\n＂,sum*1.0/n*100);  }  }
　　这种方法就叫做前缀和，用这种方法简单了很多。当然前缀和还有其他应用，例如：
　　如果给你一个数组 arr[]，然后进行 m 次询问，每次询问输入两个数 i，j（i <= j）。要求你输出 arr[i] ~ arr[j] 这个区间的和。这个时候就可以使用前缀和的方式了。前缀和的构造也是很好构造的，例如 arr[] 变成前缀和的构造方式如下for(inti=1;i<arr.length;i++){  arr[i]=arr[i]+arr[i-1];  }
　　前缀和看起来还是挺简单的，不过在做题中，或许会有意想不到的作用，例如这次的笔试，所以今天给大家讲解一下。
　　最后我再问你一个和前缀和类似的问题，给你一串长度为n的数列a1,a2,a3……an，要求对a[i]~a[j]进行m次操作：
　　操作一：将a[i]~a[j]内的元素都加上P
　　操作二：将a[i]~a[j]内的元素都减去P
　　最后再给出一个询问求a[i]-a[j]内的元素之和。
　　这个你会怎么做呢？这个时候就涉及到差分的知识了，不过它和前缀和类似，感兴趣的可以研究一下。
　　最后
　　这里关于笔试题有几点建议，由于笔试题大多数都需要我们处理输入输出，而像 leetcode，剑指 offer 都是不需要我们处理这些的，所以会不熟悉，所以我建议可以去刷下往年的真题熟悉一下。
　　还有就是大部分都是可以直接暴力的，然后能拿 20%~30%的分数，想了十分钟还是没好的思路的，建议直接暴力。
　　还有就是有时候笔试是不准你用本地 IDE 的，所以我建议平时刷题的时候，直接再网页打代码，别跑到本地 IDE 打好再粘贴过来。