第一题我记得是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;
}
}