关注
第一题我记得是100%。思路是预读入所有查询,然后由小到大排序。再从小到大遍历一遍所有区间,边遍历边从排好序的查询中不断拿出这区间的查询。 public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = sc.nextInt();
}
int apl[] = new int[n];
apl[0] = a[0];
for (int i = 1; i < n; ++i) {
apl[i] = apl[i - 1] + a[i];
}
int m = sc.nextInt();
Node nodes[] = new Node[m];
for (int i = 0; i < m; ++i) {
int c = sc.nextInt();
nodes[i] = new Node(c, i);
}
Arrays.sort(nodes, new Node(0, 0));
int cur = 0;
for (int i = 0; i < n; ++i) {
int left = i == 0 ? 1 : apl[i - 1] + 1;
int right = apl[i];
while (nodes[cur].value <= right && nodes[cur].value >= left) {
nodes[cur].ord = i + 1;
nodes[cur].value = nodes[cur].index;
if (++cur == m)
break;
}
if (cur == m)
break;
}
Arrays.sort(nodes, new Node(0, 0));
for (int i = 0; i < m; ++i)
System.out.println(nodes[i].ord);
}
}
class Node implements Comparator<Node> {
int value;
int index;
int ord;
public Node(int a, int b) {
value = a;
index = b;
}
public int compare(Node o1, Node o2) {
return o1.value - o2.value;
}
}
查看原帖
点赞 1
相关推荐
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
616510次浏览 10482人参与
# 金融银行面经 #
3306次浏览 94人参与
# 秋招开了,你想投哪些公司呢 #
112564次浏览 3217人参与
# 五一之后,实习真的很难找吗? #
9961次浏览 64人参与
# 我想象的工作vs实际工作 #
87060次浏览 1491人参与
# 浅聊一下我实习的辛苦费 #
77429次浏览 719人参与
# 简历中的项目经历要怎么写 #
414100次浏览 6947人参与
# 租房前辈的忠告 #
28056次浏览 1953人参与
# 你已经投递多少份简历了 #
279672次浏览 4254人参与
# 华为开奖那些事 #
685748次浏览 5922人参与
# 春招你拿到offer了吗 #
351459次浏览 5220人参与
# 我的成功项目解析 #
78756次浏览 2309人参与
# 机械人怎么评价今年的华为 #
63903次浏览 513人参与
# 我的上岸简历长这样 #
154160次浏览 3083人参与
# 华为工作体验 #
19691次浏览 161人参与
# 快手工作体验 #
52625次浏览 989人参与
# 晒一晒我的offer #
3162835次浏览 52718人参与
# 我发现了面试通关密码 #
316935次浏览 6098人参与
# 第一次面试 #
46777次浏览 732人参与
# 你的简历改到第几版了 #
290806次浏览 4427人参与