关注
二分,我上来就是用二分做的,没有用遍历查询,因为我知道网易的题目复杂度卡的很严,能用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
* */
}
查看原帖
点赞 2
相关推荐
06-01 21:54
湖南科技大学 嵌入式软件工程师 点赞 评论 收藏
分享
牛客热帖
更多
- 1... 腾讯提前批后台开发凉经teg1.2W
- 2... 百度提前批一面9482
- 3... 回忆录:后端鼠鼠苦苦哀求日常实习5366
- 4... 大三双非水产专业上岸阿里后端(一)2713
- 5... 去一座新的城市,开始一段新的旅途2414
- 6... 一线城市生存成本分析:月薪多少才够用?2118
- 7... 秋招offer选择 美团or快手1673
- 8... 焦虑麻了1620
- 9... 天塌了,自制力差,学了一学期的JavaSE,暑假玩了四五天天,花了八九天把笔记都看了了一遍发现记不住,就花了九天去学MySQL,然后再回过来练习Javase面试,随机抽了两个题目,线程的生命周期,ArrayList和linkedlist的区别,一点也讲不出来,我是不是不适合走后端🤯🤯🤯备受打击,现在se也不想复习了,脑子一团乱糊感觉知识进不去😭😭😭下学期就大三了,我还是民办三本,😭我该何去何从🤡1533
- 10... 实习转正,看的不只是硬实力1463
正在热议
更多
# 风评不好的公司,你会去吗? #
37063次浏览 226人参与
# 假如你的老板掉河里,你的工作能为他做什么 #
31037次浏览 380人参与
# 第一份工作应该选高薪还是热爱? #
70353次浏览 671人参与
# 职场新人体验 #
2676次浏览 31人参与
# 你觉得早上几点上班合适? #
73443次浏览 308人参与
# 学历贬值真的很严重吗? #
26020次浏览 179人参与
# 推荐一首陪你工作的歌吧 #
15071次浏览 99人参与
# 秋招签约后的心态变化 #
83711次浏览 820人参与
# 听劝,这个公司值得去吗 #
487384次浏览 1709人参与
# 双非能在秋招上岸吗? #
223054次浏览 1180人参与
# 外包能不能当跳板? #
37704次浏览 228人参与
# 面试被问第一学历差时该怎么回答 #
137738次浏览 853人参与
# 打工人的工作餐日常 #
54655次浏览 430人参与
# 大学最后一个寒假,我想…… #
47276次浏览 576人参与
# 反问环节如何提问 #
93627次浏览 1938人参与
# 一人推荐一个值得去的通信/硬件公司 #
186916次浏览 1861人参与
# 月薪多少能在一线城市生存 #
35379次浏览 351人参与
# 我想象的实习vs现实的实习 #
288306次浏览 2244人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
93117次浏览 685人参与
# 你上一次加班是什么时候? #
89596次浏览 574人参与