第十四届蓝桥杯省赛真题——平均（AC）

￡神魔★判官ぃ 2024-04-20 11:58 73阅读 0赞

#### 目录 ####

*  1. 平均
 *   *  1. 问题描述
     *  2. 输入格式
     *  3. 输出格式
     *  4. 样例输入
     *  5. 样例输出
     *  6. 样例说明
     *  7. 评测用例规模与约定
     *  8. 原题链接
 *  2. 解题思路
 *  3. AC\_Code

## 1. 平均 ##

前置知识点：贪心

### 1. 问题描述 ###

有一个长度为  n n n 的数组（ n n n 是  10 10 10 的倍数），每个数  a i a\_i ai 都是区间  \[ 0 , 9 \] \[0, 9\] \[0,9\] 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第  i i i 个数的代价为  b i b\_i bi，他想更改若干个数的值使得这  10 10 10 种数出现的次数相等（都等于  n 10 \\frac\{n\}\{10\} 10n），请问代价和最少为多少。

### 2. 输入格式 ###

输入的第一行包含一个正整数  n n n。

接下来  n n n 行，第  i i i 行包含两个整数  a i , b i a\_i, b\_i ai,bi ，用一个空格分隔。

### 3. 输出格式 ###

输出一行包含一个正整数表示答案。

### 4. 样例输入 ###

10
    1 1
    1 2
    1 3
    2 4
    2 5
    2 6
    3 7
    3 8
    3 9
    4 10

### 5. 样例输出 ###

### 6. 样例说明 ###

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

### 7. 评测用例规模与约定 ###

对于  20 20 20% 的评测用例， n ≤ 1000 n \\leq 1000 n≤1000；

对于所有评测用例， n ≤ 1 0 5 n \\leq 10^5 n≤105， 0 < b i ≤ 2 × 1 0 5 0 < b\_i \\leq 2 \\times 10^5 0<bi≤2×105。

### 8. 原题链接 ###

[平均][Link 1]

## 2. 解题思路 ##

对于任意一个数字  i ∈ \[ 0 , 9 \] i \\in\[0,9\] i∈\[0,9\] ，设它的出现次数为  x x x，我们进行分类讨论：

*  若  x > n 10 x> \\dfrac\{n\}\{10\} x>10n，则我们需要将改变其中  y = x − n 10 y=x- \\dfrac\{n\}\{10\} y=x−10n 个数字，从贪心策略考虑我们应选择该数字中代价前  y y y 小的位置进行改变。
 *  若  x < n 10 x< \\dfrac\{n\}\{10\} x<10n，说明该数字不需要进行改变。

通过上述分析，我们可以按照  a i a\_i ai 进行分组，将每个组的  b i b\_i bi 进行排序。然后遍历数字  i ∈ \[ 0 , 9 \] i \\in\[0,9\] i∈\[0,9\]，累加每个数字需要改变的最小代价即为答案。

## 3. AC\_Code ##

*  C++

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    
    int n;
    vector<int> e[10];
    int main()
    {
        
    	ios_base :: sync_with_stdio(false);
    	cin.tie(0); cout.tie(0);
    	cin >> n;
    	for (int i = 0; i < n; ++i) {
        
    		int a, v;
    		cin >> a >> v;
    		e[a].push_back(v);
    	}
    	LL ans = 0;
    	for (int i = 0; i <= 9; ++i) {
        
    		if (e[i].size() > n / 10) {
        
    			sort(e[i].begin(), e[i].end(), greater<int>());
    			for (int j = n / 10; j < (int)e[i].size(); ++j) {
        
    				ans += e[i][j];
    			}
    		}
    	}
    	cout << ans << '\n';
    	return 0;
    }

*  Java

import java.util.*;
    import java.io.*;
    
    public class Main {
        
        static int n;
        static ArrayList<Integer>[] e = new ArrayList[10];
        
        public static void main(String[] args) throws IOException {
        
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st;
            n = Integer.parseInt(br.readLine());
            for (int i=0; i<10; i++) e[i] = new ArrayList<>();
            
            for (int i=0; i<n; i++) {
        
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                e[a].add(v);
            }
            
            long ans = 0;
            for (int i=0; i<=9; i++) {
        
                if (e[i].size() > n / 10) {
        
                    Collections.sort(e[i], Collections.reverseOrder());
                    for (int j=n/10; j<e[i].size(); j++) {
        
                        ans += e[i].get(j);
                    }
                }
            }
            
            System.out.println(ans);
        }
    }

*  Python

import sys
    from operator import itemgetter
    
    n = int(sys.stdin.readline())
    e = [[] for _ in range(10)]
    
    for _ in range(n):
        a, v = map(int, sys.stdin.readline().split())
        e[a].append(v)
    
    ans = 0
    
    for i in range(10):
        if len(e[i]) > n // 10:
            e[i].sort(reverse=True)
            for j in range(n // 10, len(e[i])):
                ans += e[i][j]
    
    print(ans)

[Link 1]: https://www.lanqiao.cn/problems/3532/learning/