【备战秋招】每日一题:2023.03.26-阿里OD机试(第三题)-数组之和最小值

为了更好的阅读体检，可以查看我的算法学习网站
在线评测链接:P1119

题目内容

塔子哥是一个热爱数学的年轻数学家，他对数字和因子分解有着深入的研究。

有一天，他在一次偶然的探索中发现了一款神奇的游戏，名为“除数游戏”。

在这个游戏中，玩家需要在一个整数数组 $a$ 中选择一个大于$1$的数字 $a_i$ ，并将其除以其中一个素因子 $p$ （素因子是能被 $a_i$ 整除的素数）。接着，玩家可以继续将新数字除以素因子，直到进行了 $k$ 次操作。

塔子哥很快就意识到，这个游戏可以为他的研究提供很多有用的信息。他开始探究在最多进行 $k$ 次操作的情况下，玩家能够通过该游戏达到的最小数组总和是多少？

输入描述

第一行输入两个正整数$n$和$k$，代表数组大小以及操作次数。

第二行输入$n$个正整数$a_i$，代表数组的元素。

$1\le n,k\le 200000$

$1\le a_i\le 10^6$

输出描述

一个整数，代表操作后的所有元素最小的和。

样例

输入

5 2
1 2 3 4 5

输出

9

思路

贪心+优先队列+数论优化

1.贪心策略：由于要最小化数组的总和，那么对于某一个数$a_i$ , 要除一定是除它最大的质因子$maxfactor(a_i)$。 这样下降的最多，下降量为:${\Delta }_i=a_i-maxfactor(a_i)$ 。所以显然每一次操作我们肯定是选择$max({\Delta }_i)$ 的位置$i$ 。然后还需要更新这个值。

2.引入高级数据结构：数据量比较大，为了能够快速实现我们这个贪心策略，我们需要一个可以快速 1.寻找最大值 2.删除最大值 3.插入值 的数据结构。这个显然可以使用优先队列维护。

3.引入数论优化:在优先队列的排序过程中，由于我们需要获取$maxfactor$ , 这个东西如果每次都暴力获得，复杂度为$O(\sqrt{V})$ ,那么导致总复杂度为$O(k\ast logn\ast \sqrt{V})$ 。 这是不可接受的(虽然期望复杂度无法达到这么高，但是我们总是希望有更优的解法！)。所以我们需要先预处理出$[1,V=1e6]$ 中的所有数的$maxfactor(i)$ 。

这个预处理方法，我们可以直接使用埃式筛的方法，转移伪代码如下:

for i in 2 ... V:if maxfactor[i] : continuefor j in i -> V , step = imaxfactor[j] = max(maxfactor[j] , i)

这样一来，
$$maxfactor(i)=\{\begin{array}{cc}0& i\in prime\\ maxPrimeFactorofi& other\end{array}$$

最后，如果用一句话解释这个题的本质，就是TopK变种罢了 ， 具体细节见代码！

类似题目推荐

LeetCode

见 贪心 - 代码随想录 . 这个只是入门，刷完也并不意味着能做出这题。

CodeFun2000

提供一些贪心题

P1014 2022.10.8-美团春招-塔子玩游戏

开胃菜1

P1211 塔子大厂真题模拟赛-第一题-魔法石(Ⅰ)

开胃菜2

P1279 2023.05.06-春招-第三题-塔子哥的游戏

同样是贪心 + 优先队列的经典题目！推荐做一做！

P1239 2023.04.20-华为od-第一题-总最快检测效率

同样是贪心 + 优先队列的经典题目！推荐做一做！

P1148 2023.4.3-阿里巴巴-研发岗-第三题-又一个数论题

虽然不是贪心题。但是也是常见算法套上了数论的优化！

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 +5;
#define ll long long
int f[maxn] , a[maxn];
// 优先队列的节点
struct Node {int x;// 定义顺序bool operator < (const Node & a) const {int g1 = x - x / f[x];int g2 = a.x - a.x / f[a.x];// 优先下降量大的放堆顶return g1 < g2;}
};
priority_queue<Node> q;
int main (){int n , k;// f 就是 上文的maxfactor , 即最大质因数f[1] = 1;for (int i = 2 ; i < maxn ; i++){if (f[i] != 0) continue;for (int j = i ; j < maxn ; j += i){f[j] = max(f[j] , i);}}cin >> n >> k;// 把a[i] 都放入堆，同时获得最大值ll sum = 0;for (int i = 1 ; i <= n ; i++){cin >> a[i];sum += a[i];q.push({a[i]});}// 模拟操作while (k--){// 每次从堆顶拿出下降量最多的元素Node g = q.top();q.pop();// 更新总和sum -= g.x;sum += g.x / f[g.x];// 重新放入堆q.push({g.x / f[g.x]});}// 输出总和cout << sum << endl;return 0;
}

python

from random import *
import sys
from collections import * 
from math import * 
from functools import *
from heapq import *def solve(n,k,arr):mx = max(arr)tot = sum(arr)#f 就是 上文的maxfactor , 即最大质因数f = list(range(mx+1))for i in range(2,mx+1):if f[i] != i: continuefor j in range(i*2,mx+1,i):f[j] = i hq = []# 先把所有元素的可能序列都先全部放到序列中for a in arr:while a > 1:hq.append(a//f[a]-a)a //= f[a]# 建堆heapify(hq)# 取前k大for _ in range(k):if not hq: break tot += heappop(hq)return tot  # 读入
n, k = list(map(int,input().split()))
arr = list(map(int,input().split()))
print(solve(n,k,arr))

Java

import java.util.*;
public class Main {static int MAXN = 1000010;static int[] prime = new int[MAXN];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();prime[1] = 1;PriorityQueue<Node> pq = new PriorityQueue<>();isPrime();// 先将n个数放入优先队列for (int i = 0; i < n; i++) {int x = sc.nextInt();Node node = new Node(x, prime[x]);pq.offer(node);}// 模拟while (k-- > 0){Node node = pq.poll();int data = node.data;int x = data / node.prime;pq.offer(new Node(x, prime[x]));}long ans = 0;while (!pq.isEmpty()){ans += pq.poll().data;}System.out.println(ans);}// 求最大素数private static void isPrime() {for (int i = 2; i < MAXN; i++){if (prime[i] == 0){for (int j = i; j < MAXN; j += i){prime[j] = i;}}}}// 自定义排序static class Node implements Comparable<Node>{int data;int prime;public Node(int data, int prime) {this.data = data;this.prime = prime;}@Overridepublic int compareTo(Node o) {// 下降量最大优先return (o.data - o.data / o.prime) - (this.data - this.data / this.prime);}}
}

Go

package mainimport ("container/heap""fmt"
)const maxn = 1e6 + 5type Node struct {x int
}type PriorityQueue []Nodefunc (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {g1 := pq[i].x - pq[i].x/f[pq[i].x]g2 := pq[j].x - pq[j].x/f[pq[j].x]// 优先下降量大的放堆顶return g1 > g2
}
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }func (pq *PriorityQueue) Push(x interface{}) {node := x.(Node)*pq = append(*pq, node)
}func (pq *PriorityQueue) Pop() interface{} {n := len(*pq)node := (*pq)[n-1]*pq = (*pq)[:n-1]return node
}var f [maxn]int
var a [maxn]intfunc main() {var n, k int// f 就是 上文的 maxfactor，即最大质因数f[1] = 1for i := 2; i < maxn; i++ {if f[i] != 0 {continue}for j := i; j < maxn; j += i {f[j] = max(f[j], i)}}fmt.Scan(&n, &k)// 把 a[i] 都放入堆，同时获得最大值var sum int64 = 0pq := make(PriorityQueue, n)for i := 0; i < n; i++ {fmt.Scan(&a[i])sum += int64(a[i])pq[i] = Node{a[i]}}heap.Init(&pq)// 模拟操作for i := 0; i < k; i++ {// 每次从堆顶拿出下降量最多的元素g := heap.Pop(&pq).(Node)// 更新总和sum -= int64(g.x)sum += int64(g.x / f[g.x])// 重新放入堆heap.Push(&pq, Node{g.x / f[g.x]})}// 输出总和fmt.Println(sum)
}func max(x, y int) int {if x > y {return x}return y
}

Js

注意：已知的OJ上的JavaScript都不提供优先队列,要手写优先队列，这里塔子哥提供一种实现。

// 基于堆实现优先队列 , 函数名参考Java实现的priorityQueue
class Pqueue {constructor(cpr) {this.queue = [];this.size = 0;this.cpr = cpr;}swap(i, j) {let tmp = this.queue[i];this.queue[i] = this.queue[j];this.queue[j] = tmp;}// 上浮swim() {let ch = this.queue.length - 1;while (ch !== 0) {let fa = Math.floor((ch - 1) / 2);const ch_node = this.queue[ch];const fa_node = this.queue[fa];if (this.cpr(ch_node, fa_node) < 0) {this.swap(ch, fa);ch = fa;} else {break;}}}// 下沉sink() {let fa = 0;while (true) {let ch_left = 2 * fa + 1;let ch_right = 2 * fa + 2;let ch_max;let ch_max_node;const fa_node = this.queue[fa];const ch_left_node = this.queue[ch_left];const ch_right_node = this.queue[ch_right];if (ch_left_node && ch_right_node) {// 注意这里应该要>=0，因为左边优先级高if (this.cpr(ch_left_node, ch_right_node) <= 0) {ch_max = ch_left;ch_max_node = ch_left_node;} else {ch_max = ch_right;ch_max_node = ch_right_node;}} else if (ch_left_node && !ch_right_node) {ch_max = ch_left;ch_max_node = ch_left_node;} else if (!ch_left_node && ch_right_node) {ch_max = ch_right;ch_max_node = ch_right_node;} else {break;}// 注意这里应该要>0，因为父优先级高if (this.cpr(ch_max_node, fa_node) < 0) {this.swap(ch_max, fa);fa = ch_max;} else {break;}}}// 向优先队列中加入元素offer(ele) {this.queue.push(ele);this.size++;this.swim();}// 取出最高优先级元素poll() {this.swap(0, this.queue.length - 1);this.size--;const ans = this.queue.pop();this.sink();return ans;}// 只使用最高优先级元素，不取出peek() {return this.queue[0];}
}// 正片const maxn = 1e6 + 5;
let f = new Array(maxn).fill(0);
let a = new Array(maxn).fill(0);let q = new Pqueue((a , b) => {let g1 = a - Math.floor(a / f[a]);let g2 = b - Math.floor(b / f[b]);return g2 - g1;
});
f[1] = 1;
for (let i = 2; i < maxn; i++) {if (f[i] !== 0) continue;for (let j = i; j < maxn; j += i) {f[j] = Math.max(f[j], i);}
}process.stdin.resume();
process.stdin.setEncoding("utf-8");
let input = "";
process.stdin.on("data", (data) => {input += data;return;
});
process.stdin.on("end", () => {const lines = input.trim().split("\n");var [n, k] = lines[0].split(" ").map(Number);var a = lines[1].split(' ').map(Number);let sum = 0;for (let i = 0 ; i < n; i++) {sum += a[i];q.offer(a[i]);}while (k--) {let x = q.poll();sum -= x;sum += Math.floor(x / f[x]);q.offer(Math.floor(x / f[x]));}console.log(sum);
});

题目内容均收集自互联网，如如若此项内容侵犯了原著者的合法权益，可联系我: (CSDN网站注册用户名: 塔子哥学算法) 进行删除