首页 > 试题广场 >

最小代价

[编程题]最小代价
  • 热度指数:657 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给你一个数组,让第个数加一的代价是b_i,你可以求出让数组a,每个数各不相同的最小代价吗?

输入描述:
第一行一个整数,表示数组长度

第二行个整数a_i,表示数组

第三行个整数b_i,表示第个增加1的代价


输出描述:
一个整数表示结果.
示例1

输入

5
1 2 3 4 5
1 1 1 1 1

输出

0

说明

不用任何操作
示例2

输入

3
1 1 2
4 5 3

输出

7

说明

先把第1个数字1加1,此时代价为4,a数组为2 1 2。然后再把第三个数字2加1,此时代价为4+3=7,a数组为2 1 3。
import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
        int [][]tmp= new int[n][2];
        for(int i = 0;i<n;i++){
            tmp[i][0]=sc.nextInt();
        }
        for(int i = 0;i<n;i++){
            tmp[i][1]= sc.nextInt();
        }
        Arrays.sort(tmp,new Comparator<int []>(){
           public int compare(int[]o1,int[]o2){
               if(o1[0]==o2[0])return o1[1]-o2[1];
               return o1[0]-o2[0];
           }
        });
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2){
                return o2-o1;
            }
        });
        int cur = tmp[0][0];
        long all = 0;
        long ans = 0;
        for(int[]price:tmp){
            if(!queue.isEmpty() && price[0]!=cur){
                while(!queue.isEmpty() && price[0]!=cur++){
                    all -= queue.poll();
                    ans+=all;
                }
                cur=price[0];
            }
            queue.add(price[1]);
            all+=price[1];
        }
        while(!queue.isEmpty()){
            all-=queue.poll();
            ans+=all;
        }
        System.out.println(ans);
      
        
        
     
    }

}

发表于 2022-03-23 16:54:11 回复(0)
Python版本,通过部分组,供参考
n = int(input())
list1 = input().split()
cost1 = input().split()

for i in range(n):
    list1[i] = int(list1[i])
    cost1[i] = int(cost1[i])

i = 0
sum_cost = 0
cost2 = cost1[:]
cost2.sort()

while i < n:
    ind = cost1.index(cost2[i])

    cnt = 0
    i += 1

    for j in range(n):
        if list1[ind] == list1[j]:
            cnt += 1
    if cnt > 1:
        list1[ind] += 1
        sum_cost += cost1[ind]
        i = 0

print(sum_cost)


发表于 2022-03-17 14:41:59 回复(0)