题目描述
在系统、网络均正常的情况下组织核酸采样员和志愿者对人群进行核酸检测筛查。
每名采样员的效率不同，采样效率为N人/小时。
由于外界变化，采样员的效率会以M人/小时为粒度发生变化，M为采样效率浮动粒度，M=N*10%，输入保证N*10%的结果为整数。
采样员效率浮动规则：采样员需要一名志愿者协助组织才能发挥正常效率，在此基础上，每增加一名志愿者，效率提升1M，最多提升3M；如果没有志愿者协助组织，效率下降2M。
怎么安排速度最快？求总最快检测效率（总检查效率为各采样人员效率值相加）。
输入描述
第一行：第一个值，采样员人数，取值范围[1, 100]；第二个值，志愿者人数，取值范围[1, 500]；
第二行：各采样员基准效率值（单位人/小时），取值范围[60, 600]，保证序列中每项值计算10%为整数。
输出描述
第一行：总最快检测效率（单位人/小时）
用例
| 输入 | 2 2 200 200 |
| 输出 | 400 |
| 说明 | 输入需要保证采样员基准效率值序列的每个值*10%为整数。 |
逻辑分析解法
假设有x个采样员（正常采样效率为a1,a2,a3,…,ax），y个志愿者，初始时，不给采样员安排志愿者，则可以得到所有采样员的裸奔状态的采样效率 = (a1 * 0.8) + (a2 * 0.8) + (a3 * 0.8) + … + (ax * 0.8)。
然后，我们收集每个采样员的如下数据：
- 增加第一个采样员，新增的效率
- 增加第两个采样员，新增的效率
- 增加第三个采样员，新增的效率
- 增加第四个采样员，新增的效率
比如，对于采样员a1而言：
- 增加第一个采样员，新增效率 a1 * 0.2
- 增加第两个采样员，新增效率 a1 * 0.1
- 增加第三个采样员，新增效率 a1 * 0.1
- 增加第四个采样员，新增效率 a1 * 0.1
我们将每个采样员上面数据收集到一个列表add中，对add进行降序（从大到小排序），则前y个新增效率，即最多新增效率。
这里可能有人会产生疑问？对于每个采样员元而言，其新增的效率都是递进的，比如增加第二个采样员，得到的新增效率，必须要在增加第一个采样员的基础上，上面对add列表进行排序后，是否还能保证取到的前y个效率能保证这个递进关系呢？
答案是可以。因为，本题已经固定了新增效率的规则：
采样员需要一名志愿者协助组织才能发挥正常效率（即提升2M效率），在此基础上，每增加一名志愿者，效率提升1M
因此，一个采样员想要提升1M效率前面必须要先提升2M效率，而add列表进行降序的话，必然是2M在前，1M在后。
因此，add列表降序，不会破会单个采样员的新增效率的递进关系。
那么多个采样员的新增效率混在一起排序，会产生影响吗？答案是也不会，相当于是有多个降序列表，比如：
- [8, 4, 4, 4]
- [10, 5, 5, 5]
- [6, 3, 3, 3]
将这多个降序列表进行合并后，再次降序
- [10, 8, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3]
则这个合并列表，其实还是维持着各自采样员的新增效率递进关系：
- [10, 8, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3]
- [10, 8, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3]
- [10, 8, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3]
JavaScript算法源码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
// x是采样员人数，y是志愿者人数
const [x, y] = (await readline()).split(" ").map(Number);
// x个采样员的正常效率
const normals = (await readline()).split(" ").map(Number);
// base 记录每个采样员的裸奔效率
let base = 0;
// add 记录每个采样员的递进新增效率
const add = [];
for (let normal of normals) {
// M为采样效率浮动粒度
const m = normal * 0.1;
// 采样员正常效率是10M，如果没有志愿者协助组织，效率下降2M，即8M
base += 8 * m;
// 增加第1个采样员的新增效率， 增加第2个采样员的新增效率，增加第3个采样员的新增效率，增加第4个采样员的新增效率，
add.push(2 * m, m, m, m);
}
// 对所有新增效率降序
add.sort((a, b) => b - a);
// 裸奔效率 + 前y大的新增效率 就是 最高效率
const ans = base + add.slice(0, y).reduce((a, b) => a + b);
console.log(ans);
})();
Java算法源码
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// x是采样员人数，y是志愿者人数
int x = sc.nextInt();
int y = sc.nextInt();
// x个采样员的正常效率
int[] normals = new int[x];
for (int i = 0; i < x; i++) normals[i] = sc.nextInt();
// base 记录每个采样员的裸奔效率
int base = 0;
// increase 记录每个采样员的递进新增效率
ArrayList<Integer> increase = new ArrayList<>();
for (int normal : normals) {
// M为采样效率浮动粒度
int m = normal / 10;
// 采样员正常效率是10M，如果没有志愿者协助组织，效率下降2M，即8M
base += 8 * m;
// 增加第1个采样员的新增效率
increase.add(2 * m);
// 增加第2个采样员的新增效率
increase.add(m);
// 增加第3个采样员的新增效率
increase.add(m);
// 增加第4个采样员的新增效率
increase.add(m);
}
// 对所有新增效率降序
increase.sort((a, b) -> b - a);
// 裸奔效率 + 前y大的新增效率 就是 最高效率
int ans =
base
+ increase.subList(0, Math.min(y, increase.size())).stream()
.reduce(Integer::sum)
.orElse(0);
System.out.println(ans);
}
}
Python算法源码
# 输入获取
x, y = map(int, input().split()) # x是采样员人数，y是志愿者人数
normals = list(map(int, input().split())) # x个采样员的正常效率
# 算法入口
def getResult():
# base 记录每个采样员的裸奔效率
base = 0
# increase 记录每个采样员的递进新增效率
increase = []
for normal in normals:
# M为采样效率浮动粒度
m = normal // 10
# 采样员正常效率是10M，如果没有志愿者协助组织，效率下降2M，即8M
base += 8 * m
# 增加第1个采样员的新增效率
increase.append(2 * m)
# 增加第2个采样员的新增效率
increase.append(m)
# 增加第3个采样员的新增效率
increase.append(m)
# 增加第4个采样员的新增效率
increase.append(m)
# 对所有新增效率降序
increase.sort(reverse=True)
# 裸奔效率 + 前y大的新增效率 就是 最高效率
return base + sum(increase[:y])
# 算法调用
print(getResult())
贪心思维解法
用例意思是：
有两个采样员，两个志愿者。
两个采样员的正常效率都是200，但是要给每个采样员配一个志愿者才能发挥正常效率。
现在刚好采样员和志愿者是一比一，因此可以发挥出总效率是：200 + 200 = 400。
如果，我们给一个采样员配两个志愿者，那么该采样员发挥的效率是：200 + 200 * 10% = 220。
但是另一名采样员就没有志愿者了，因此发挥不了正常效率，200 – 200 * 20% = 160，此时总效率是220 + 160 = 380。
因此，总最快效率是400。
需要注意的是，用例中采样员的正常效率只是凑巧相同，很有可能出现一个采样员的正常效率极高，一个采样员的正常效率极低的情况。
我的解题思路如下：
首先分两种情况：
1、志愿者数量少于采样员
2、志愿者数量不少于采样员
对于情况1，我们应该将不多的志愿者优先分配给高效率的采样员，默认一比一分配。
接下来，我们应该考虑，剥夺低效率的采样员的志愿者 给 高效率的采样员，只要 高效率采样员增加的10%的效率 可以大于 低效率采样员减少的20%的效率。
其中还要考虑，高效率的采样员最多可以追加3个志愿者，即最多增加30%的效率。如果最高效率的采样员已经提升30%效率，则第二高效率的采样员称为最高优先级，继续上面剥夺逻辑。
对于情况2，我们应该先按一比一的方式，给每个采样员分配一个志愿者。
然后，如果还多出志愿者的话，则优先分配给高效率的采样员，同样需要注意每个采样员最追加3个志愿者。
当多出的志愿者分配完后，我们需要考虑剥夺低效率的采样员的志愿者 给 高效率的采样员，只要 高效率采样员增加的10%的效率 可以大于 低效率采样员减少的20%的效率。逻辑同情况1。
根据ant_shi网友的指正，上面解析对于志愿者超出采样员数量四倍时的情况考虑不够全面：
另外，对于情况2而言，如果采样员：志愿者 的比例，超过了1：4，那么超出4倍采样员范围的志愿者将没有效率提升作用，因此有效志愿者数量最多是四倍的采样员数量。
JavaScript算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
const [x, y] = lines[0].split(" ").map(Number);
const arrX = lines[1].split(" ").map(Number);
console.log(getResult(arrX, x, y));
lines.length = 0;
}
});
/**
*
* @param {*} x 采样员人数
* @param {*} arr 每个采样员的正常效率
* @param {*} y 志愿者人数
*/
function getResult(arr, x, y) {
// 按照正常效率降序
arr.sort((a, b) => b - a);
let max = 0;
// 如果志愿者少于采样员，则优先将志愿者分配给正常效率高的采样员
if (y < x) {
for (let i = 0; i < x; i++) {
// 0~y-1范围内高效率的采样员优先获得一个志愿者，因此保持正常效率，而y~x-1范围内的低效率采样员则没有志愿者，效率下降20%
max += i < y ? arr[i] : arr[i] * 0.8;
}
let i = 0;
let j = y - 1;
let count = 0;
while (i < j) {
// 接下来，我们需要比较0~y-1范围，最高效率的采样员上升10%的效率 是否大于 最低效率的采样员下降20%的效率
if (arr[i] * 0.1 > arr[j] * 0.2) {
// 如果大于，则将效率低的采样员的志愿者分配给效率高的采样员
max += arr[i] * 0.1 - arr[j] * 0.2;
// 由于一个采样员最多只能提升30%，即除了一个基础志愿者外，最多再配3个志愿者，多配了也没用
if (++count === 3) {
count = 0;
i++;
}
j--;
} else {
break;
}
}
}
// 如果志愿者 不少于 采样员，那么默认情况下每个采样员都分配一个志愿者
else {
// 如果志愿者人数超过采样员四倍，则多出来的志愿者就没有作用了
if (y >= 4 * x) {
y = 4 * x;
}
// 每个采样员都默认发挥正常效率
max = arr.reduce((p, c) => p + c);
// surplus记录每个采样员分配一个志愿者后，还多出来的志愿者
let surplus = y - x;
let i = 0;
let j = x - 1;
let count = 0;
// 优先将多出来的志愿者分配给高效率的采样员
while (surplus > 0) {
max += arr[i] * 0.1;
surplus--;
if (++count === 3) {
count = 0;
i++;
}
}
// 多出来的志愿者分配完后，则继续考虑剥夺低效率采样员的志愿者给高效率的采样员
while (i < j) {
if (arr[i] * 0.1 > arr[j] * 0.2) {
max += arr[i] * 0.1 - arr[j] * 0.2;
if (++count === 3) {
count = 0;
i++;
}
j--;
} else {
break;
}
}
}
return max;
}
优化逻辑后代码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
const [x, y] = lines[0].split(" ").map(Number);
const arrX = lines[1].split(" ").map(Number);
console.log(getResult(arrX, x, y));
lines.length = 0;
}
});
/**
*
* @param {*} x 采样员人数
* @param {*} arr 每个采样员的正常效率
* @param {*} y 志愿者人数
*/
function getResult(arr, x, y) {
// 按照正常效率降序
arr.sort((a, b) => b - a);
let max = 0;
let i;
let j;
let count = 0;
// 如果志愿者少于采样员，则优先将志愿者分配给正常效率高的采样员
if (y < x) {
for (let i = 0; i < x; i++) {
// 0~y-1范围内高效率的采样员优先获得一个志愿者，因此保持正常效率，而y~x-1范围内的低效率采样员则没有志愿者，效率下降20%
max += i < y ? arr[i] : arr[i] * 0.8;
}
i = 0;
j = y - 1;
}
// 如果志愿者 不少于 采样员，那么默认情况下每个采样员都分配一个志愿者
else {
// 如果志愿者人数超过采样员四倍，则多出来的志愿者就没有作用了
if (y >= 4 * x) {
y = 4 * x;
}
// 每个采样员都默认发挥正常效率
max = arr.reduce((p, c) => p + c);
// surplus记录每个采样员分配一个志愿者后，还多出来的志愿者
let surplus = y - x;
i = 0;
j = x - 1;
// 优先将多出来的志愿者分配给高效率的采样员
while (surplus > 0) {
max += arr[i] * 0.1;
surplus--;
if (++count === 3) {
count = 0;
i++;
}
}
}
// 多出来的志愿者分配完后，则继续考虑剥夺低效率采样员的志愿者给高效率的采样员
while (i < j) {
// 接下来，我们需要比较最高效率的采样员上升10%的效率 是否大于 最低效率的采样员下降20%的效率
if (arr[i] * 0.1 > arr[j] * 0.2) {
// 如果大于，则将效率低的采样员的志愿者分配给效率高的采样员
max += arr[i] * 0.1 - arr[j] * 0.2;
// 由于一个采样员最多只能提升30%，即除了一个基础志愿者外，最多再配3个志愿者，多配了也没用
if (++count === 3) {
count = 0;
i++;
}
j--;
} else {
break;
}
}
return max;
}
Java算法源码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
Integer[] arrX = new Integer[x];
for (int i = 0; i < x; i++) {
arrX[i] = sc.nextInt();
}
System.out.println(getResult(arrX, x, y));
}
public static int getResult(Integer[] arr, int x, int y) {
// 按照正常效率降序
Arrays.sort(arr, (a, b) -> b - a);
int max = 0;
int count = 0;
int i;
int j;
// 如果志愿者少于采样员，则优先将志愿者分配给正常效率高的采样员
if (y < x) {
// 0~y-1范围内高效率的采样员优先获得一个志愿者，因此保持正常效率，而y~x-1范围内的低效率采样员则没有志愿者，效率下降20%
for (int k = 0; k < x; k++) {
max += k < y ? arr[k] : arr[k] * 0.8;
}
i = 0;
j = y - 1;
}
// 如果志愿者 不少于 采样员，那么默认情况下每个采样员都分配一个志愿者
else {
// 如果志愿者人数超过采样员四倍，则多出来的志愿者就没有作用了
if (y >= 4 * x) {
y = 4 * x;
}
// 每个采样员都默认发挥正常效率
for (Integer val : arr) {
max += val;
}
// surplus记录每个采样员分配一个志愿者后，还多出来的志愿者
int surplus = y - x;
i = 0;
j = x - 1;
// 优先将多出来的志愿者分配给高效率的采样员
while (surplus > 0) {
max += arr[i] * 0.1;
surplus--;
if (++count == 3) {
count = 0;
i++;
}
}
}
// 志愿者分配完后，则继续考虑剥夺低效率采样员的志愿者给高效率的采样员
while (i < j) {
// 如果最高效率的采样员上升10%的效率 是否大于 最低效率的采样员下降20%的效率，那么就值得剥夺
if (arr[i] * 0.1 > arr[j] * 0.2) {
max += arr[i] * 0.1 - arr[j] * 0.2;
// 由于一个采样员最多只能提升30%，即除了一个基础志愿者外，最多再配3个志愿者，多配了也没用
if (++count == 3) {
count = 0;
i++;
}
j--;
} else {
break;
}
}
return max;
}
}
Python算法源码
# 输入获取
x, y = map(int, input().split())
arr = list(map(int, input().split()))
# 算法入口
def getResult(arr, x, y):
# 按照正常效率降序
arr.sort(reverse=True)
maxV = 0
count = 0
i = None
j = None
# 如果志愿者少于采样员，则优先将志愿者分配给正常效率高的采样员
if y < x:
# 0~y-1范围内高效率的采样员优先获得一个志愿者，因此保持正常效率，而y~x-1范围内的低效率采样员则没有志愿者，效率下降20%
for k in range(x):
maxV += arr[k] if k < y else arr[k] * 0.8
i = 0
j = y - 1
# 如果志愿者 不少于 采样员，那么默认情况下每个采样员都分配一个志愿者
else:
# 如果志愿者人数超过采样员四倍，则多出来的志愿者就没有作用了
if y >= 4 * x:
y = 4 * x
# 每个采样员都默认发挥正常效率
for val in arr:
maxV += val
# surplus记录每个采样员分配一个志愿者后，还多出来的志愿者
surplus = y - x
i = 0
j = x - 1
# 优先将多出来的志愿者分配给高效率的采样员
while surplus > 0:
maxV += arr[i] * 0.1
surplus -= 1
count += 1
if count == 3:
count = 0
i += 1
# 志愿者分配完后，则继续考虑剥夺低效率采样员的志愿者给高效率的采样员
while i < j:
# 如果最高效率的采样员上升10%的效率 是否大于 最低效率的采样员下降20%的效率，那么就值得剥夺
if arr[i] * 0.1 > arr[j] * 0.2:
maxV += arr[i] * 0.1 - arr[j] * 0.2
# 由于一个采样员最多只能提升30%，即除了一个基础志愿者外，最多再配3个志愿者，多配了也没用
count += 1
if count == 3:
count = 0
i += 1
j -= 1
else:
break
return int(maxV)
# 算法调用
print(getResult(arr, x, y))优先队列解法
本题最优思路是采用优先队列解法。
即将所有采样员加入（大顶堆）优先队列中，优先级是：该采样员新增一名志愿者，所能提升的效率。
初始时，加入优先队列的采样员都不搭配采样员，此时新增一名志愿者，每个采样员都能提升20%，但是由于基准效率base不同，因此实际每个采样员提升的效率值为base * 0.2。
之后，我们取出堆顶最大提升效率的采样员，为其新增一名志愿者：
- 如果其已有志愿者数量为0，则新增一名志愿者后，恢复为base效率
- 如果其已有志愿者数量<=3，则新增一名志愿者后，其总效率 += base * 0.1
- 如果其已有志愿者数量 > 3，即至少为4，则再新增一名志愿者，不会带来效率提升，即新增效率为0
当我们更新完取出的采样员的志愿者数量和总效率后，将其重新压入优先队列，进行排序。
最后，当志愿者用完了，或者所有采样员都安排了4名志愿者了，则结束上面操作。
接下来就是取出优先队列的所有采样员，并累加他们的总效率作为题解。
JavaScript算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
const [x, y] = lines[0].split(" ").map(Number);
const arrX = lines[1].split(" ").map(Number);
console.log(getResult(arrX, x, y));
lines.length = 0;
}
});
/**
*
* @param {*} arr 每个采样员的正常效率
* @param {*} x 采样员人数
* @param {*} y 志愿者人数
*/
function getResult(arr, x, y) {
// 大顶堆优先队列，堆顶元素总是：新增一个志愿者后，提升效率最多的采样员
const pq = new PriorityQueue((a, b) => getAdd(b) - getAdd(a));
// 将所有采样员员加入优先队列，初始时采样员都不搭配志愿者
for (let base of arr) {
pq.offer(new Sample(base));
}
// 只要还有志愿者，就将其分配给采样员
while (y > 0) {
// 如果堆顶采样员已有四个志愿者，那么该采样员能提升的效率为0，说明此时提升0的效率就是所有采样员中能提升的最大效率，即说明所有采样员都安排到了四个采样员，因此再增加志愿者也不会带来效率提升
if (pq.size == 0 || pq.peek().volunteer == 4) break;
// 如果上一步不成立，则取出堆顶采样员
const s = pq.poll();
// 为其新增一个志愿者，并提升相应效率
s.total += getAdd(s);
s.volunteer += 1;
// 重新压入队列
pq.offer(s);
y--;
}
let ans = 0;
while (pq.size > 0) ans += pq.poll().total;
return ans;
}
class Sample {
constructor(base) {
this.volunteer = 0; // 该采样员搭配的志愿者人数
this.base = base; // 该采样员的基准效率
this.total = base * 0.8; // 该采样员的搭配志愿者后的总效率,初始时采样员没有搭配志愿者，则效率只有base*0.8
}
}
// 采样员s增加一名志愿者能提升的效率
function getAdd(s) {
// 如果当前采样员没有志愿者，则新增一名志愿者可以提升base * 20%的效率
if (s.volunteer == 0) return s.base * 0.2;
// 如果当前采样员搭配的志愿者数量小于等于3个，则说明再新增一个志愿者，可以提升base * 10%的效率
else if (s.volunteer <= 3) return s.base * 0.1;
// 如果当前采样员已有4个志愿者，则再新增一个志愿者，不能提升效率，即提升效率为0
else return 0;
}
// 基于堆实现优先队列
class PriorityQueue {
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];
}
}
Java算法源码
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
Integer[] arrX = new Integer[x];
for (int i = 0; i < x; i++) {
arrX[i] = sc.nextInt();
}
System.out.println(getResult(arrX, x, y));
}
/**
* @param arr 各采样员基准效率值（单位人/小时） [60, 600]
* @param x 采样员人数 [1, 100]
* @param y 志愿者人数 [1, 500]
* @return 总最快检测效率（单位人/小时）
*/
public static int getResult(Integer[] arr, int x, int y) {
// 大顶堆优先队列，堆顶元素总是：新增一个志愿者后，提升效率最多的采样员
PriorityQueue<Sampler> pq = new PriorityQueue<>((a, b) -> (int) (getAdd(b) - getAdd(a)));
// 将所有采样员员加入优先队列，初始时采样员都不搭配志愿者
for (int base : arr) {
pq.offer(new Sampler(0, base));
}
// 只要还有志愿者，就将其分配给采样员
while (y > 0) {
// 如果堆顶采样员已有四个志愿者，那么该采样员能提升的效率为0，说明此时提升0的效率就是所有采样员中能提升的最大效率，即说明所有采样员都安排到了四个采样员，因此再增加志愿者也不会带来效率提升
if (pq.isEmpty() || pq.peek().volunteer == 4) break;
// 如果上一步不成立，则取出堆顶采样员
Sampler s = pq.poll();
// 为其新增一个志愿者，并提升相应效率
s.total += getAdd(s);
s.volunteer += 1;
// 重新压入队列
pq.offer(s);
y--;
}
double ans = 0;
while (!pq.isEmpty()) ans += pq.poll().total;
return (int) ans;
}
// 采样员s增加一名志愿者能提升的效率
public static double getAdd(Sampler s) {
// 如果当前采样员没有志愿者，则新增一名志愿者可以提升base * 20%的效率
if (s.volunteer == 0) return s.base * 0.2;
// 如果当前采样员搭配的志愿者数量小于等于3个，则说明再新增一个志愿者，可以提升base * 10%的效率
else if (s.volunteer <= 3) return s.base * 0.1;
// 如果当前采样员已有4个志愿者，则再新增一个志愿者，不能提升效率，即提升效率为0
else return 0;
}
}
// 采样员类
class Sampler {
int volunteer = 0; // 该采样员搭配的志愿者人数
double base = 0; // 该采样员的基准效率
double total = 0; // 该采样员的搭配志愿者后的总效率
public Sampler(int volunteer, double base) {
this.volunteer = volunteer;
this.base = base;
this.total = base * 0.8; // 初始时采样员没有搭配志愿者，则效率只有base*0.8
}
}
Python算法源码
import queue
# 输入获取
x, y = map(int, input().split())
arr = list(map(int, input().split()))
def getAdd(s):
"""
:param s: 采样员对象
:return: 假设采样员s增加一名志愿者能提升的效率
"""
if s.volunteer == 0: # 如果当前采样员没有志愿者，则新增一名志愿者可以提升base * 20%的效率
return s.base * 0.2
elif s.volunteer <= 3: # 如果当前采样员搭配的志愿者数量小于等于3个，则说明再新增一个志愿者，可以提升base * 10%的效率
return s.base * 0.1
else: # 如果当前采样员已有4个志愿者，则再新增一个志愿者，不能提升效率，即提升效率为0
return 0
class Sampler:
def __init__(self, volunteer, base):
"""
:param volunteer: 该采样员搭配的志愿者人数
:param base: 该采样员的基准效率
"""
self.volunteer = volunteer
self.base = base
self.total = base * 0.8 # 初始时采样员没有搭配志愿者，则效率只有base*0.8
def __lt__(self, other):
return getAdd(self) > getAdd(other) # 基于大顶堆排序，优先级为：增加一名志愿者能提升的效率
# 算法入口
def getResult(arr, x, y):
"""
:param arr: 各采样员基准效率值（单位人/小时） [60, 600]
:param x: 采样员人数 [1, 100]
:param y: 志愿者人数 [1, 500]
:return: 总最快检测效率（单位人/小时）
"""
# 优先队列
pq = queue.PriorityQueue()
# 将所有采样员员加入优先队列，初始时采样员都不搭配志愿者
for base in arr:
pq.put(Sampler(0, base))
# 只要还有志愿者，就将其分配给采样员
while y > 0:
# 如果堆顶采样员已有四个志愿者，那么该采样员能提升的效率为0，说明此时提升0的效率就是所有采样员中能提升的最大效率，即说明所有采样员都安排到了四个采样员，因此再增加志愿者也不会带来效率提升
if pq.qsize() == 0 or pq.queue[0].volunteer == 4:
break
# 如果上一步不成立，则取出堆顶采样员
s = pq.get()
# 为其新增一个志愿者，并提升相应效率
s.total += getAdd(s)
s.volunteer += 1
# 重新压入队列
pq.put(s)
y -= 1
ans = 0
while pq.qsize() > 0:
ans += pq.get().total
return int(ans)
# 算法调用
print(getResult(arr, x, y))
免责声明：
1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文
评论0