塔子哥的数组2-美团2023笔试(codefun2000)

题目链接
塔子哥的数组2-美团2023笔试(codefun2000)

题目内容

塔子哥被给定一个长度为n的数组，她最多可以进行m次操作，每次操作如下:
1.选择两个下标 i,j(1<i<j<n) 根据样例1的答案来看，这里是(1<=i<j<=n)
2.选择两个整数x,y 满足条件：x∗y=ai∗aj
3.ai:=x , aj:=y
他只能操作m 次 ， 目标是使得最后数组中的元素的总和尽可能大

输入描述

输出描述

输出一个整数，表示最后数组中元素总和最大值。
由于答案可能很大，输出取模1e9+7 意义下的结果

样例1

输入

6 2
1 2 3 4 5 6

输出

128

样例解释

其实，使用大顶堆来解这题，不是很好处理，由于中间的计算结果可能会超出long long类型的最大值，对这个值进行取模后，压入堆中，本应放在堆顶的元素，可能因为取模后，没有放在堆顶，导致下次取的元素不对
题解：每次将数组中的最大的两个元素a,b替换成a*b和1，进行m次操作，得到最后的数组

题解1

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 1e5 + 10;

int n, m, a[N];
LL sum;

priority_queue<LL> pq; // 大顶堆 
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]),sum += a[i], pq.push(1LL*a[i]);
	while(m--){
		LL a = pq.top() % MOD; pq.pop();
		LL b = pq.top() % MOD; pq.pop(); // 取大顶堆的前2个最大的元素 
		
		sum = (sum - a - b)%MOD; 
		sum = (sum + a*b + 1)%MOD;
		pq.push(1LL);pq.push(a*b);
	}
	
	printf("%lld\n", sum);
	return 0;
}