华师一附中OI组

标题: 2760: 完美的序列(sequence) [打印本页]

作者: admin 时间: 2021-10-29 08:32
标题: 2760: 完美的序列(sequence)
题目描述
LYK认为一个完美的序列要满足这样的条件：对于任意两个位置上的数都不相同。然而并不是所有的序列都满足这样的条件。
于是LYK想将序列上的每一个元素都增加一些数字(当然也可以选择不增加)，使得整个序列变成美妙的序列。
具体地，LYK可以花费1点代价将第i个位置上的数增加1，现在LYK想花费最小的代价使得将这个序列变成完美的序列。

输入格式(sequence.in)
第一行一个数n，表示数字个数。
接下来一行n个数ai表示LYK得到的序列。

输出格式(sequence.out)
一个数表示变成完美的序列的最小代价。

输入样例
4
1 1 3 2

输出样例
3

数据范围
对于30%的数据n<=5。
对于60%的数据n<=1000。
对于80%的数据n<=30000，ai<=3000。
对于100%的数据n<=100000，1<=ai<=100000。

作者: admin 时间: 2021-10-29 08:44
最笨的做法显然是枚举每个数增加几次，显然每个数增加的次数不超过n。比如样例1132，
第一是数是1，前面没有，可以保留；
第二是数是2，前面有，必须改，改成多少呢？先试试改成2吧！也可以改成后面第一个没有的4，这个作为第二种方法等下验算。
第三是数是3，前面没有，可以保留；
第四数是2，前面有，只能改成4。
至此全部改完，费用是1+2=3。
若按第二种方法把第二个数直接改成4，那么代价也是3。
这种方法是不是证确的方法呢?

对于此样例，最后成型的数组一定是1234，总和是10，原始数据是1132总和是7，怎么改都要增加3，不管是改一个还是改3个。所以不影响答案。
然后我们发现，数的位置也不影响答案，所以我们可以先排序，这样就更方便。

欢迎光临华师一附中OI组 (http://hsyit.cn/)