A15236. River Locks
编程题
普及/提高-
知识点
题目描述
Recently in Divanovo, a huge river locks system was built. There are now $n$ locks, the $i$ -th of them has the volume of $v_i$ liters, so that it can contain any amount of water between $0$ and $v_i$ liters. Each lock has a pipe attached to it. When the pipe is open, $1$ liter of water enters the lock every second.
The locks system is built in a way to immediately transfer all water exceeding the volume of the lock $i$ to the lock $i + 1$ . If the lock $i + 1$ is also full, water will be transferred further. Water exceeding the volume of the last lock pours out to the river.
The picture illustrates $5$ locks with two open pipes at locks $1$ and $3$ . Because locks $1$ , $3$ , and $4$ are already filled, effectively the water goes to locks $2$ and $5$ .Note that the volume of the $i$ -th lock may be greater than the volume of the $i + 1$ -th lock.
To make all locks work, you need to completely fill each one of them. The mayor of Divanovo is interested in $q$ independent queries. For each query, suppose that initially all locks are empty and all pipes are closed. Then, some pipes are opened simultaneously. For the $j$ -th query the mayor asks you to calculate the minimum number of pipes to open so that all locks are filled no later than after $t_j$ seconds.
Please help the mayor to solve this tricky problem and answer his queries.
The locks system is built in a way to immediately transfer all water exceeding the volume of the lock $i$ to the lock $i + 1$ . If the lock $i + 1$ is also full, water will be transferred further. Water exceeding the volume of the last lock pours out to the river.
The picture illustrates $5$ locks with two open pipes at locks $1$ and $3$ . Because locks $1$ , $3$ , and $4$ are already filled, effectively the water goes to locks $2$ and $5$ .Note that the volume of the $i$ -th lock may be greater than the volume of the $i + 1$ -th lock.
To make all locks work, you need to completely fill each one of them. The mayor of Divanovo is interested in $q$ independent queries. For each query, suppose that initially all locks are empty and all pipes are closed. Then, some pipes are opened simultaneously. For the $j$ -th query the mayor asks you to calculate the minimum number of pipes to open so that all locks are filled no later than after $t_j$ seconds.
Please help the mayor to solve this tricky problem and answer his queries.
输入格式
The first lines contains one integer $n$ ( $1 \le n \le 200\,000$ ) — the number of locks.
The second lines contains $n$ integers $v_1, v_2, \dots, v_n$ ( $1 \le v_i \le 10^9$ )) — volumes of the locks.
The third line contains one integer $q$ ( $1 \le q \le 200\,000$ ) — the number of queries.
Each of the next $q$ lines contains one integer $t_j$ ( $1 \le t_j \le 10^9$ ) — the number of seconds you have to fill all the locks in the query $j$ .
The second lines contains $n$ integers $v_1, v_2, \dots, v_n$ ( $1 \le v_i \le 10^9$ )) — volumes of the locks.
The third line contains one integer $q$ ( $1 \le q \le 200\,000$ ) — the number of queries.
Each of the next $q$ lines contains one integer $t_j$ ( $1 \le t_j \le 10^9$ ) — the number of seconds you have to fill all the locks in the query $j$ .
输出格式
Print $q$ integers. The $j$ -th of them should be equal to the minimum number of pipes to turn on so that after $t_j$ seconds all of the locks are filled. If it is impossible to fill all of the locks in given time, print $-1$ .
输入输出样例
输入 #1
5 4 1 5 4 1 6 1 6 2 3 4 5
输出 #1
-1 3 -1 -1 4 3
输入 #2
5 4 4 4 4 4 6 1 3 6 5 2 4
输出 #2
-1 -1 4 4 -1 5
说明/提示
There are $6$ queries in the first example test.
In the queries $1, 3, 4$ the answer is $-1$ . We need to wait $4$ seconds to fill the first lock even if we open all the pipes.
In the sixth query we can open pipes in locks $1$ , $3$ , and $4$ . After $4$ seconds the locks $1$ and $4$ are full. In the following $1$ second $1$ liter of water is transferred to the locks $2$ and $5$ . The lock $3$ is filled by its own pipe.
Similarly, in the second query one can open pipes in locks $1$ , $3$ , and $4$ .
In the fifth query one can open pipes $1, 2, 3, 4$ .
In the queries $1, 3, 4$ the answer is $-1$ . We need to wait $4$ seconds to fill the first lock even if we open all the pipes.
In the sixth query we can open pipes in locks $1$ , $3$ , and $4$ . After $4$ seconds the locks $1$ and $4$ are full. In the following $1$ second $1$ liter of water is transferred to the locks $2$ and $5$ . The lock $3$ is filled by its own pipe.
Similarly, in the second query one can open pipes in locks $1$ , $3$ , and $4$ .
In the fifth query one can open pipes $1, 2, 3, 4$ .