当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

7130:Monopoly

题目描述
Little Rabbit loves playing a tabletop game called $\textit{Monopoly}$. In the game, players roll the dice to move around the game board, buying and trading properties, and developing them with houses and hotels. Players collect rent from their opponents, with the goal being to drive them into bankruptcy.

One day, Little Rabbit invites Little Horse to play the game with him, but Little Horse stands him up. As a result, Little Rabbit can only play the game on his own. After a while, Little Rabbit finds out another way to play the game.

Let's consider the map of the game as $n$ integers $a_1,a_2,\dots,a_n$ placed in a circle. If the player lands on $a_i$, his score will change by $a_i$ points. Specifically, if $a_i>0$, his score will increase by $|a_i|$ points. If $a_i<0$, his score will decrease by $|a_i|$ points. And of course, if $a_i=0$, his score won't change.

As there is nobody else, Little Rabbit doesn't feel like rolling a dice. So he just moves on the map step by step. Formally, if he now lands on $a_i$ and $i\lt n$, he will move to $a_{i+1}$ in the next step. If he now lands on $a_n$, he will move to $a_1$ in the next step.

Initially, Little Rabbit has $0$ points, and his first step is to land on $a_1$. Little Rabbit wonders how many steps he should take at least to reach $\textbf{exactly}$ $x$ points. (Specifically, since his initial score is $0$, he needs $0$ steps to reach $0$ points.)
输入解释
The first line of the input contains an integer $T$ ($1 \le T \le 20$), indicating the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n,m \le 10^5$), indicating the number of integers on the map and the number of queries.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ($-10^9\le a_1,a_2,\dots,a_n \le 10^9$), indicating the integers on the map.

In the next $m$ lines, each line contains an integer $x$ ($-10^{12} \le x \le 10^{12}$), indicating a query.

It's guaranteed that $\sum n \le 5\times10^5$ and $\sum m \le 5\times 10^5$.
输出解释
For each query, output an integer in a single line, indicating the number of steps he should take at least to reach $\textbf{exactly}$ $x$ points. If it is impossible to reach exactly $x$ points, output $-1$.
输入样例
1
3 5
1 -3 4
1
5
2
0
-10
输出样例
1
7
3
0
-1

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-7130

最后修改于 2021-10-23T19:11:38+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
6000/3000MS(Java/Others) 262144/262144K(Java/Others)