问题描述
小蓝是一名年轻的数学家，他最近对数组的美丽值产生了浓厚的兴趣。他定义了一个数组的美丽值为任意两个数的乘积之和，即 ∑i=1n∑j=i+1n(ai×aj)∑i=1n∑j=i+1n(ai×aj)。为了深入研究这个概念，他收集了一个长度为 nn 的数组 aa。 他想知道通过 kk 次操作后，任意两个数的乘积之和最大可以达到多少。每次操作可以将数组 aa 中的任意一个数加 11。请你帮他解决这个问题，并将答案对 109+7109+7 取模。
输入格式
第一行输入两个整数 nn 和 kk ，表示 aa 的长度以及可操作次数。
第二行输入 nn 个空格隔开的整数 aiai 。
数据范围保证：1≤n≤3×1051≤n≤3×105，1≤ai,k≤1091≤ai,k≤109 。
输出格式
输出一个整数表示答案，答案需要对 109+7109+7 取模。
样例输入
2 2 4 1样例输出
12说明
样例中将 11 变为 33 后，数组的美丽值为 3×4=12。
java">import jdk.swing.interop.SwingInterOpUtils;import java.util.PriorityQueue;
import java.util.Scanner;public class MaxBeautyOfNum {static long MOD=1000000007;public static void main(String[] args){Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();long k=scanner.nextLong();long ans=0;PriorityQueue<Long> pq=new PriorityQueue<>();for(int i=0;i<n;i++){long t=scanner.nextLong();pq.add(t);}for(int i=0;i<k;i++){long min=pq.poll();min+=1;pq.add(min);}Long[] array = pq.toArray(new Long[0]);for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){ans=ans+array[i]*array[j]%MOD;}}System.out.println(ans%MOD);}
}
上面的代码会出现运行超时的情况，改进如下代码：
java">import java.util.PriorityQueue;
import java.util.Scanner;public class MaxBeautyOfNum {static long MOD = 1000000007;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();long k = scanner.nextLong();PriorityQueue<Long> pq = new PriorityQueue<>();long totalSum = 0, beauty = 0;// 初始化优先队列并计算初始总和for (int i = 0; i < n; ++i) {long t = scanner.nextLong();pq.add(t);totalSum += t;}// 计算初始美丽值Long[] initialArray = pq.toArray(new Long[0]);long t1=totalSum;for (long num : initialArray) {t1 -= num;beauty = (beauty + num * t1) % MOD;}// 执行k次操作for (long i = 0; i < k; ++i) {long min = pq.poll(); // 取出当前最小值beauty = (beauty + totalSum - min + MOD) % MOD; // 更新美丽值totalSum += 1; // 总和增加1（因为min变为min+1）min += 1; // 最小值加1pq.add(min); // 将增加后的值重新加入队列}System.out.println(beauty);}
}get到一个新技能：求数组两两乘积之和的另外一个方法：
