A14763 | Array Equalizer
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Jeevan has two arrays $a$ and $b$ of size $n$ . He is fond of performing weird operations on arrays. This time, he comes up with two types of operations:
- Choose any $i$ ( $1 \le i \le n$ ) and increment $a_j$ by $1$ for every $j$ which is a multiple of $i$ and $1 \le j \le n$ .
- Choose any $i$ ( $1 \le i \le n$ ) and decrement $a_j$ by $1$ for every $j$ which is a multiple of $i$ and $1 \le j \le n$ .
He wants to convert array $a$ into an array $b$ using the minimum total number of operations. However, Jeevan seems to have forgotten the value of $b_1$ . So he makes some guesses. He will ask you $q$ questions corresponding to his $q$ guesses, the $i$ -th of which is of the form:
- If $b_1 = x_i$ , what is the minimum number of operations required to convert $a$ to $b$ ?
Help him by answering each question.
- Choose any $i$ ( $1 \le i \le n$ ) and increment $a_j$ by $1$ for every $j$ which is a multiple of $i$ and $1 \le j \le n$ .
- Choose any $i$ ( $1 \le i \le n$ ) and decrement $a_j$ by $1$ for every $j$ which is a multiple of $i$ and $1 \le j \le n$ .
He wants to convert array $a$ into an array $b$ using the minimum total number of operations. However, Jeevan seems to have forgotten the value of $b_1$ . So he makes some guesses. He will ask you $q$ questions corresponding to his $q$ guesses, the $i$ -th of which is of the form:
- If $b_1 = x_i$ , what is the minimum number of operations required to convert $a$ to $b$ ?
Help him by answering each question.
输入格式
The first line contains a single integer $n$ $(1 \le n \le 2 \cdot 10^{5})$ — the size of arrays $a$ and $b$ .
The second line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^6)$ .
The third line contains $n$ integers $b_1, b_2, ..., b_n$ $(1 \le b_i \le 10^6$ for $i \neq 1$ ; $b_1 = -1$ , representing that the value of $b_1$ is unknown $)$ .
The fourth line contains a single integer $q$ $(1 \le q \le 2 \cdot 10^{5})$ — the number of questions.
Each of the following $q$ lines contains a single integer $x_i$ $(1 \le x_i \le 10^6)$ — representing the $i$ -th question.
The second line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^6)$ .
The third line contains $n$ integers $b_1, b_2, ..., b_n$ $(1 \le b_i \le 10^6$ for $i \neq 1$ ; $b_1 = -1$ , representing that the value of $b_1$ is unknown $)$ .
The fourth line contains a single integer $q$ $(1 \le q \le 2 \cdot 10^{5})$ — the number of questions.
Each of the following $q$ lines contains a single integer $x_i$ $(1 \le x_i \le 10^6)$ — representing the $i$ -th question.
输出格式
Output $q$ integers — the answers to each of his $q$ questions.
输入输出样例
输入 #1
2 3 7 -1 5 3 1 4 3
输出 #1
2 4 2
输入 #2
6 2 5 4 1 3 6 -1 4 6 2 3 5 3 1 8 4
输出 #2
10 29 9
Consider the first test case.
- $b_1 = 1$ : We need to convert $[3, 7] \rightarrow [1, 5]$ . We can perform the following operations: $[3, 7]$ $\xrightarrow[\text{decrease}]{\text{i = 1}}$ $[2, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 1}}$ $[1, 5]$
Hence the answer is $2$ .
- $b_1 = 4$ : We need to convert $[3, 7] \rightarrow [4, 5]$ . We can perform the following operations: $[3, 7]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 5]$ $\xrightarrow[\text{increase}]{\text{i = 1}}$ $[4, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[4, 5]$
Hence the answer is $4$ .
- $b_1 = 3$ : We need to convert $[3, 7] \rightarrow [3, 5]$ . We can perform the following operations: $[3, 7]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 5]$
Hence the answer is $2$ .
- $b_1 = 1$ : We need to convert $[3, 7] \rightarrow [1, 5]$ . We can perform the following operations: $[3, 7]$ $\xrightarrow[\text{decrease}]{\text{i = 1}}$ $[2, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 1}}$ $[1, 5]$
Hence the answer is $2$ .
- $b_1 = 4$ : We need to convert $[3, 7] \rightarrow [4, 5]$ . We can perform the following operations: $[3, 7]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 5]$ $\xrightarrow[\text{increase}]{\text{i = 1}}$ $[4, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[4, 5]$
Hence the answer is $4$ .
- $b_1 = 3$ : We need to convert $[3, 7] \rightarrow [3, 5]$ . We can perform the following operations: $[3, 7]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 5]$
Hence the answer is $2$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted