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

解题思路:

对于每个数的权重都存在一个数组中，数组从小到大排序，取前k个多余的最小权重的位置进行替换即可，用空间换时间

注意事项:

数组内有零值,需要遍历找到非0值
参考代码:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;

public class Main {
   public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
   public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
   public static PrintWriter count = new PrintWriter(new OutputStreamWriter(System.out));

   public static void main(String[] args) throws Exception {
       int n = nextInt();
       int times = n / 10;
       int[] nums0 = new int[n];
       int[] nums1 = new int[n];
       int[] nums2 = new int[n];
       int[] nums3 = new int[n];
       int[] nums4 = new int[n];
       int[] nums5 = new int[n];
       int[] nums6 = new int[n];
       int[] nums7 = new int[n];
       int[] nums8 = new int[n];
       int[] nums9 = new int[n];
       int flag0 = 0;
       int flag1 = 0;
       int flag2 = 0;
       int flag3 = 0;
       int flag4 = 0;
       int flag5 = 0;
       int flag6 = 0;
       int flag7 = 0;
       int flag8 = 0;
       int flag9 = 0;
       for(int i = 0 ; i < n ; i++){
           int num = nextInt();
           int kilo = nextInt();
           switch (num){
               case 0:{
                   nums0[flag0++] = kilo;
                   break;
               }
               case 1:{
                   nums1[flag1++] = kilo;
                   break;
               }
               case 2:{
                   nums2[flag2++] = kilo;
                   break;
               }
               case 3:{
                   nums3[flag3++] = kilo;
                   break;
               }
               case 4:{
                   nums4[flag4++] = kilo;
                   break;
               }
               case 5:{
                   nums5[flag5++] = kilo;
                   break;
               }
               case 6:{
                   nums6[flag6++] = kilo;
                   break;
               }
               case 7:{
                   nums7[flag7++] = kilo;
                   break;
               }
               case 8:{
                   nums8[flag8++] = kilo;
                   break;
               }
               case 9:{
                   nums9[flag9++] = kilo;
                   break;
               }
           }
       }
       long sum = 0;//作为总代价
       if(flag0>times){
           Arrays.sort(nums0);
           int index = 0;
           while (true){
               if(nums0[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag0 - times + index; i++){
               sum+=nums0[i];
           }
       }
       if(flag1>times){
           Arrays.sort(nums1);
           int index = 0;
           while (true){
               if(nums1[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag1 - times + index ; i++){
               sum+=nums1[i];
           }
       }
       if(flag2>times){
           Arrays.sort(nums2);
           int index = 0;
           while (true){
               if(nums2[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag2 - times + index; i++){
               sum+=nums2[i];
           }
       }
       if(flag3>times){
           Arrays.sort(nums3);
           int index = 0;
           while (true){
               if(nums3[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag3 - times + index; i++){
               sum+=nums3[i];
           }
       }
       if(flag4>times){
           Arrays.sort(nums4);
           int index = 0;
           while (true){
               if(nums4[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag4 - times + index; i++){
               sum+=nums4[i];
           }
       }
       if(flag5>times){
           Arrays.sort(nums5);
           int index = 0;
           while (true){
               if(nums5[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag5 - times + index; i++){
               sum+=nums5[i];
           }
       }
       if(flag6>times){
           Arrays.sort(nums6);
           int index = 0;
           while (true){
               if(nums6[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag6 - times + index; i++){
               sum+=nums6[i];
           }
       }
       if(flag7>times){
           Arrays.sort(nums7);
           int index = 0;
           while (true){
               if(nums7[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag7 - times + index; i++){
               sum+=nums7[i];
           }
       }
       if(flag8>times){
           Arrays.sort(nums8);
           int index = 0;
           while (true){
               if(nums8[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag8 - times + index; i++){
               sum+=nums8[i];
           }
       }
       if(flag9>times){
           Arrays.sort(nums9);
           int index = 0;
           while (true){
               if(nums9[index++]!=0){
                   break;
               }
           }
           index--;
           for(int i = index ; i < flag9 - times + index; i++){
               sum+=nums9[i];
           }
       }
       count.print(sum);
       //拿空间换时间？
       closeAll();
   }

   public static int nextInt() throws Exception {
       cin.nextToken();
       return (int) cin.nval;
   }

   public static long nextLong() throws Exception {
       cin.nextToken();
       return (long) cin.nval;
   }

   public static double nextDouble() throws Exception {
       cin.nextToken();
       return cin.nval;
   }

   public static String nextString() throws Exception {
       cin.nextToken();
       return cin.sval;
   }

   public static String Line() throws Exception {
       String p = "";
       p = in.readLine();
       return p;
   }

   public static void closeAll() throws Exception {
       count.close();
       in.close();
       out.close();
   }
}