Sleeping in Class

题目描述

奶牛 Bessie 最近很兴奋能回到线下学习！ 不幸的是，她的讲师 Farmer John 讲课非常无聊，因此她经常在课堂上睡着。 Farmer John 注意到 Bessie 上课没有专心。他让同班的另一位同学 Elsie 记录 Bessie 在一节课中睡着的次数。共有 $N$ 个课时（$2\le N\le 10^5$），Elsie 记录 Bessie 在第 $i$ 个课时中睡着了 $a_i$ 次（$1\le a_i\le 10^{18}$）。Bessie 在所有课时中睡着的总次数最多为 $10^{18}$。 Elsie 因为和 Bessie 很有竞争心，想让 Farmer John 觉得 Bessie 在每节课中睡着的次数始终一致——让问题看起来完全是 Bessie 的错，与 Farmer John 有时无聊的讲课无关。 Elsie 修改记录的唯一方式是：将两个相邻的课时合并，或将一个课时拆分为两个。例如，若 $a=[1,2,3,4,5],$，则若 Elsie 合并第二和第三个课时，记录会变为 $[1,5,4,5]$。如果随后 Elsie 选择把第三个课时拆分成两个，则记录可以变为以下任意一种：$[1,5,0,4,5]$、$[1,5,1,3,5]$、$[1,5,2,2,5]$、$[1,5,3,1,5]$ 或 $[1,5,4,0,5]$。 给定 $Q$（$1\le Q\le 10^5$）个候选数 $q_1,\ldots,q_Q$，它们是 Bessie 最不喜欢的数字的候选（$1\le q_i\le 10^{18}$）。对每个候选数，帮助 Elsie 计算她最少需要对记录进行多少次修改，才能使记录中的所有数字都变成相同的数。

输入格式

每个测试用例的第一行包含 $N$，第二行包含 $a_1,a_2,\ldots,a_N$。第三行包含 $Q$，接下来 $Q$ 行每行包含一个整数 $q_i$，表示 Bessie 最不喜欢数字的一个候选值。

输出格式

对每个 $q_i$，计算 Elsie 将记录中的每一项都变为 $q_i$ 所需的最小修改次数；若不可能则输出 $-1$。

6
1 2 3 1 1 4
7
1
2
3
4
5
6
12

6
6
4
5
-1
4
5

提示

Elsie 至少需要四次修改才能把记录变为全是 3。 1 2 3 1 1 4 -> 3 3 1 1 4 -> 3 3 1 5 -> 3 3 6 -> 3 3 3 3 将记录变为全是 5 是不可能的，因此该候选的正确输出是 $-1$。 SCORING: 在测试点 2-4 中，$N,Q\le 5000$ 在测试点 5-7 中，所有 $a_i$ 均不超过 $10^9$。 测试点 8-26 没有额外限制。 题目来源：Jesse Choe 和 Benjamin Qi

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum