CF1105A Salem and Sticks

    • 89通过
    • 113提交
  • 题目来源 CodeForces 1105A
  • 评测方式 RemoteJudge
  • 标签
  • 难度 普及-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目概述

    $Salem$ 给了你 $n$ 个木棍,它们的长度分别为 $a_1,a_2,\cdot \cdot \cdot a_n$。

    对于每一根木棍,你可以把它的长度变为任意整数(即收缩或者拉伸)。把一根木棍的长度 $a$ 变为 $b$ 将花费 $|a-b|$ 的价格。

    如果说一根木棍对于整数 $t$ 是好的,则需要满足要求 $|a_i - t| \leq 1$。

    现在 $Salem$ 让你去改变一些木棍的长度(可能全部或不改变),使所有木棍对于整数 $t$ 是好的,并让花费的价格尽可能小,$t$ 的值不是固定的值,您可以让它成为任意正整数。

    现在请你输出 $t$ 的值和最小花费的价格。如果有多种情况,请输出任意一个。

    输入输出格式

    输入格式:

    第一行,包含一个整数 $n$,表示木棍总数。$(1\leq n \leq 1000)$

    第二行,包含 $n$ 个整数,表示每一根木棍的长度 $a_i$。$(1\leq a_i \leq 1000)$

    输出格式:

    共一行,包含 $t$ 的值和所花费的最小价格,中间用空格分开。

    说明

    对于第一个样例,我们可以把长度为 $1$ 的木棍变成 $2$,长度为 $10$ 的木棍变成 $4$,将花费 $|1-2|+|10-4|=1+6=7$ 的价格,最终长度 $[2,4,4]$ 是适合 $t=3$ 的。

    对于第二个样例,我们不需要作出任何改变,所有木棍对于 $t=2$ 都是好的。

    题目描述

    Salem gave you $ n $ sticks with integer positive lengths $ a_1, a_2, \ldots, a_n $ .

    For every stick, you can change its length to any other positive integer length (that is, either shrink or stretch it). The cost of changing the stick's length from $ a $ to $ b $ is $ |a - b| $ , where $ |x| $ means the absolute value of $ x $ .

    A stick length $ a_i $ is called almost good for some integer $ t $ if $ |a_i - t| \le 1 $ .

    Salem asks you to change the lengths of some sticks (possibly all or none), such that all sticks' lengths are almost good for some positive integer $ t $ and the total cost of changing is minimum possible. The value of $ t $ is not fixed in advance and you can choose it as any positive integer.

    As an answer, print the value of $ t $ and the minimum cost. If there are multiple optimal choices for $ t $ , print any of them.

    输入输出格式

    输入格式:

    The first line contains a single integer $ n $ ( $ 1 \le n \le 1000 $ ) — the number of sticks.

    The second line contains $ n $ integers $ a_i $ ( $ 1 \le a_i \le 100 $ ) — the lengths of the sticks.

    输出格式:

    Print the value of $ t $ and the minimum possible cost. If there are multiple optimal choices for $ t $ , print any of them.

    输入输出样例

    输入样例#1: 复制
    3
    10 1 4
    
    输出样例#1: 复制
    3 7
    
    输入样例#2: 复制
    5
    1 1 2 2 3
    
    输出样例#2: 复制
    2 0
    

    说明

    In the first example, we can change $ 1 $ into $ 2 $ and $ 10 $ into $ 4 $ with cost $ |1 - 2| + |10 - 4| = 1 + 6 = 7 $ and the resulting lengths $ [2, 4, 4] $ are almost good for $ t = 3 $ .

    In the second example, the sticks lengths are already almost good for $ t = 2 $ , so we don't have to do anything.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。