购物

题目地址

购物

题目描述

在遥远的东方，有一家糖果专卖店。 这家糖果店将会在每天出售一些糖果，它每天都会生产出m个糖果，第i天的第j个糖果价格为C[i][j]元。 现在的你想要在接下来的n天去糖果店进行选购，你每天可以买多个糖果，也可以选择不买糖果，但是最多买m个。（因为最多只生产m个）买来糖果以后，你可以选择吃掉糖果或者留着之后再吃。糖果不会过期，你需要保证这n天中每天你都能吃到至少一个糖果。 这家店的老板看你经常去光顾这家店，感到非常生气。（因为他不能好好睡觉了）于是他会额外的要求你支付点钱。具体来说，你在某一天购买了 k 个糖果，那么你在这一天需要额外支付 k2 的费用。 那么问题来了，你最少需要多少钱才能达成自己的目的呢？

思路

由于我们选择糖果时肯定是从小到大选择,但考虑到有一个额外的代价,因此我们需要将这个额外的代价加入到糖果的价格中去,可以算出,我们每多选一个糖果,额外的代价是(k+1)^2-k^2=2*k+1,因此将糖果原价和额外的代价相加后用优先队列维护即可,由于要保证每天都要有1颗糖果吃,所以不能直接把所有糖果一次性全部加入到优先队列中去,否则可能会出现某天没有糖果吃的情况(糖果全是在后面几天买的,前几天没买一个)。而应该排好序后就把当天的糖果全部加入并选择一颗代价最小的,这样可以保证这一天吃的糖果一定是在这一天或者是在这一天的前面买的。

代码

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[]arg_s){
        Scanner in=new Scanner(System.in);
        int m,n;
        long res=0;
        n=in.nextInt();
        m=in.nextInt();
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        int[]s=new int[m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                s[j]=in.nextInt();
            }
            Arrays.sort(s);
            for(int k=0;k<m;k++){
                pq.offer(s[k]+2*k+1);
            }
            res+=pq.poll();
        }
        System.out.println(res);
    }
}