【牛客网NC75-20.7.24-堆】链接：牛客网NC75
题意：
文章图片
输入：给定n,c。给定a数组，ai表示第i个数的大小。1<=n<=2*1e5,1<=c<=100,1≤ai≤102
输出：计算的时间
分析：每一次都有两数相加，每次等价于两数之和乘c,而我们可以发现，总的操作次数是固定的，所以为了使时间最小，小的数应该先开始加使得大的数乘c的次数尽可能的少
思路：维护一个小顶堆，通过数组也可以实现，从尾部插入，上浮来维护小顶堆，从头部取得最小值，以尾部元素代替头部元素，从头部元素下沉来维护小顶堆。
看到有人用优先队列priority_queue,这个简单，好像优先队列也是堆实现的吧。
代码：
import java.util.*;
public class Solution {
/**
* 返回一个数字表示输出计算n个数字和的最小花费的时间。
* @param n int整型 表示有n个数。
* @param c int整型 参数c
* @param a int整型一维数组 ai表示第i个数的大小
* @return long长整型
*/
public long solve (int n, int c, int[] a) {
// write code here
int[] b=new int[200005];
int cnt=0;
for(int i=0;
i1){
long tem1=delete(b,cnt);
cnt--;
long tem2=delete(b,cnt);
cnt--;
sum+=(tem1+tem2)*c;
insert(b,cnt,(int)(tem1+tem2));
cnt++;
}
return sum;
}
static void insert(int[] a,int n,int k){
a[n]=k;
if(n==0)return;
int chi=n;
int par=(n-1)/2;
while(par>=0) {
if (a[chi] >= a[par]) break;
int temp = a[chi];
a[chi] = a[par];
a[par] = temp;
chi=par;
par=(chi-1)/2;
}
}
static int delete(int[] a,int n){
int ans=a[0];
a[0]=a[n-1];
int par=0;
int leftchi=1;
int rightchi=2;
while(leftchi=a[par])break;
int tem=a[k];
a[k]=a[par];
a[par]=tem;
par=k;
leftchi=par*2+1;
rightchi=par*2+2;
}
return ans;
}
}
推荐阅读
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- 每日一题|牛客网NC31、29-20.8.1-贪心
- 牛客网NC26-20.8.4-树
- 牛客网NC18、12-20.8.2-模拟、递推
- 【每日一题】LeetCode. 50. Pow(x, n)