3179 问题 D: 蓝桥杯2023年第十四届省赛真题-平均

时间限制: 3s 内存限制: 512MB 提交: 4760 解决: 1086
题目描述
有一个长度为 n 的数组（n 是 10 的倍数），每个数 ai 都是区间 [0, 9] 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 i 个数的代价为bi，他想更改若干个数的值使得这 10 种数出现的次数相等（都等于n/10），请问代价和最少为多少。
输入
输入的第一行包含一个正整数 n 。
接下来 n 行，第 i 行包含两个整数 ai , bi ，用一个空格分隔。
输出
输出一行包含一个正整数表示答案。
样例输入
10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10
样例输出
27
提示

只更改第 1, 2, 4, 5, 7, 8 个数，需要花费代价 1 + 2 + 4 + 5 + 7 + 8 = 27 。


对于 20% 的评测用例，n ≤ 1000；
对于所有评测用例，n ≤ 100000, 0 < bi ≤ 2 × 105 。 



                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
第十四届蓝桥杯（省赛）真题（基础部分，适合所有同学），已经确定报名名单的同学一定要参加，欢迎其他同学积极练习...................................
                        

                    

                

                

                    

                        
比赛状况