102773: [AtCoder]ABC277 D - Takahashi's Solitaire
Description
Score : $400$ points
Problem Statement
Takahashi has $N$ cards in his hand. For $i = 1, 2, \ldots, N$, the $i$-th card has an non-negative integer $A_i$ written on it.
First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).
- Let $X$ be the integer written on the last card put on the table. If his hand contains cards with the integer $X$ or the integer $(X+1)\bmod M$ written on them, freely choose one of those cards and put it on the table. Here, $(X+1)\bmod M$ denotes the remainder when $(X+1)$ is divided by $M$.
Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $2 \leq M \leq 10^9$
- $0 \leq A_i \lt M$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
9 7 3 0 2 5 5 3 0 6 3
Sample Output 1
11
Assume that he first puts the fourth card ($5$ is written) on the table and then performs the following.
- Put the fifth card ($5$ is written) on the table.
- Put the eighth card ($6$ is written) on the table.
- Put the second card ($0$ is written) on the table.
- Put the seventh card ($0$ is written) on the table.
Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is $3 + 2 + 3 +3 = 11$. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.
Sample Input 2
1 10 4
Sample Output 2
0
Sample Input 3
20 20 18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12
Sample Output 3
99
Input
题意翻译
【题面翻译】 给定 $n$ 张牌，每张牌上有一个数字 $a_i$。 你要先选一张牌放在桌子上。假设当前最后一张放置的牌为 $x$，接下来，你每次只能放写着 $x$ 或 $(x + 1) \bmod m$ 的牌。 一直操作下去。你需要让你手上剩下的牌的总和**最小**。 translated by @[liangbowen](https://www.luogu.com.cn/user/367488). 【输入格式】 第一行两个数 $n$，$m$。 接下来 $n$ 个数，表示卡牌上的数字 $a_i$。 【输出格式】 输出最小和值。 【数据范围】 $1 \le n \le 2 \times 10^5$ $2 \le m \le 10^9$ 保证 $0 \le a_i < m$。Output
问题描述
高桥手里有$N$张卡片。 对于$i = 1, 2, \ldots, N$，第$i$张卡片上写有一个非负整数$A_i$。
首先，高桥将从他的手中自由选择一张卡片放在桌子上。 然后，他想做多少次就做多少次（可能为零次）以下操作。
- 设$X$为最后放在桌子上的卡片上的整数。如果他的手中包含写有整数$X$或整数$(X+1)\bmod M$的卡片，自由选择其中一张并将其放在桌子上。其中，$(X+1)\bmod M$表示当$(X+1)$被$M$除时的余数。
打印他手中最终剩余卡片上的整数之和的最小可能值。
约束条件
- $1 \leq N \leq 2 \times 10^5$
- $2 \leq M \leq 10^9$
- $0 \leq A_i \lt M$
- 输入中的所有值都是整数。
输入
输入以标准输入的以下格式给出：
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
打印答案。
样例输入1
9 7 3 0 2 5 5 3 0 6 3
样例输出1
11
假设他首先将第四张卡片（上面写着$5$）放在桌子上，然后进行以下操作。
- 将第五张卡片（上面写着$5$）放在桌子上。
- 将第八张卡片（上面写着$6$）放在桌子上。
- 将第二张卡片（上面写着$0$）放在桌子上。
- 将第七张卡片（上面写着$0$）放在桌子上。
那么，第一、三、六、九张卡片将最终留在他的手中，这些卡片上的整数之和为$3 + 2 + 3 +3 = 11$。 这是他手中最终剩余卡片上的整数之和的最小可能值。
样例输入2
1 10 4
样例输出2
0
样例输入3
20 20 18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12
样例输出3
99