#abc334c. C - Socks 2
C - Socks 2
Score : points
问题描述
高桥有对袜子,其中第对包含两只颜色为的袜子。有一天,在整理他的抽屉后,高桥发现他丢失了颜色分别为的各一只袜子,因此他决定用剩下的只袜子来制作对新的袜子,每对包含两只袜子。定义一双由颜色和颜色的袜子组成的袜子对的奇怪度为,高桥希望尽量减少总奇怪度。
求在用剩下的袜子制作对时,可能达到的最小总奇怪度。注意,如果是奇数,则会有一只袜子未被包括在任何一对中。
以上为通义千问 qwen-max 翻译,仅供参考。
Problem Statement
Takahashi has pairs of socks, and the -th pair consists of two socks of color . One day, after organizing his chest of drawers, Takahashi realized that he had lost one sock each of colors , so he decided to use the remaining socks to make new pairs of socks, each pair consisting of two socks. The weirdness of a pair of a sock of color and a sock of color is defined as , and Takahashi wants to minimize the total weirdness.
Find the minimum possible total weirdness when making pairs from the remaining socks. Note that if is odd, there will be one sock that is not included in any pair.
Constraints
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the minimum total weirdness as an integer.
Sample Input 1
4 2
1 3
Sample Output 1
2
Below, let denote a pair of a sock of color and a sock of color .
There are socks of colors , respectively. Creating the pairs results in a total weirdness of , which is the minimum.
Sample Input 2
5 1
2
Sample Output 2
0
The optimal solution is to make the pairs and leave one sock of color as a surplus (not included in any pair).
Sample Input 3
8 5
1 2 4 7 8
Sample Output 3
2
update @ 2024/3/10 01:21:12