网易内推笔试讨论

我本人，二分查找第一个大于某数的数，然后减一，不知道为什么只过了30%?

用了Arrays.binarySearch 超时的路过

#include <iostream> #include <vector> using namespace std; int main(){     int n;     cin>>n;     vector<int> tmp;     for(int i=0;i<n;++i){         int appleNum;         cin>>appleNum;         int val;         if(i==0)             val=appleNum;         else             val=appleNum+tmp[i-1];         tmp.push_back(val);     }     int m;     cin>>m;     vector<int> res;     for(int j=0;j<m;++j){         int query;         cin>>query;         int low=0;         int high=n-1;         while(low<=high){             int mid=low+(high-low)/2;             if(tmp[mid]<query)                 low=mid+1;             else if(tmp[mid]>query){                 if(mid>0 && tmp[mid-1]<quary){                     res.push_back(mid+1);                     break;                 }                 else if(mid==0){                     res.push_back(mid+1);                     break;                 }                 else                     high=mid-1;             }             else{                 res.push_back(mid+1);                 break;             }         }     }     for(int i=0;i<m;++i)         if(i!=m-1)             cout<<res[i]<<endl;         else             cout<<res[i];     return 0; }

二分，我上来就是用二分做的，没有用遍历查询，因为我知道网易的题目复杂度卡的很严，能用O(longn)做的O(n)绝对过不了。但是第一次提交也没能AC。我就想到了累加的时候可能超过int所能表示的最大值，换成long型就A了。一下是我的代码，写的很挫，见谅！ public class FengShou {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         while(in.hasNext()){             int n = in.nextInt();             long[] arr = new long[n];             long count = 0;             for(int i = 0; i < n; i++){                 count += in.nextInt();                 arr[i] = count;             }             int m = in.nextInt();             long[] queries = new long[m];             int[] res = new int[m];             for(int i = 0; i < m; i++){                 queries[i] = in.nextLong();             }             for(int i = 0; i < m; i++){                 if(queries[i] <= arr[n - 1])                     res[i] = lower_bound(arr, 0, arr.length, queries[i]);             }                          for(int i : res){                 System.out.println(i + 1);             }          }         in.close();     }               public static int lower_bound(long[] arr, int begin, int end, long tag){         while(begin < end){             int mid = (begin + end) / 2;             if(arr[mid] < tag){                 begin = mid + 1;             }else                 end = mid;         }         return begin;     }           /* test case: 5  2 7 3 4 9 3 1 25 11  * */ }

楼主你知道为啥了吗？这个试题牛客上有了吗？可愁死我了

……二分超时一般就是你退不出循环（比如继续循环条件写成了min<max，实际上是min<=max……） 和时间复杂度没什么关系

二分30%……，才知道前面累加数组就O n了

用的二分，100%