昨晚学妹参加了B站秋招笔试,还想考考我?

学妹昨晚参加了B站的2022届秋招算法笔试,做完给我发来了一道题,想考考我,说挺难的。

我看了两分钟,给她发去了我的思路。然后学妹一眼就看懂了,立马秒过。

那么这道题到底是怎么做的呢?

题目要求将$n$个数切分成$k$块,求每块的序号乘上该块内数字之和的最大值。

那么首先我们可以用$S_i$来表示前缀和,也就是$S_i = \sum_{j < i}{a_j}$。

然后假设$k$个子序列中,第$i$个子序列的末尾元素为$a_{d_i}$,其中$1 \le i \le k$。那么第$i$个子序列的元素和就可以用前缀和来表示为$S_{d_i} - S_{d_{i-1}}$。

然后题目要求的最大值就可以表示为:
$$
\sum_{1 \le i \le k}{i \cdot (S_{d_i} - S_{d_{i-1}})}
$$

展开并化简就可以得到:
$$
-\sum_{0 \le i \le k-1}{S_{d_i}} + k \cdot S_{d_k}
$$

后面一项$k \cdot S_{d_k}$就是整个数组之和的$k$倍,是一个定值。所以要求这个式子的最大值,就是求$\sum_{0 \le i \le k-1}{S_{d_i}}$的最小值。

又因为$S_{d_0} = 0$,所以就是求$\sum_{1 \le i \le k-1}{S_{d_i}}$的最小值。

可以发现,这$k-1$个前缀和其实是互不干扰的,所以只需要对所有的前缀和进行排序,取最小的$k-1$个就行了。

C++代码如下:

#include <stdio.h>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 300010;

ll a[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &a[i]);
        if (i) a[i] += a[i-1];
    }
    sort(a, a+n-1);
    ll res = 0;
    for (int i = 0; i < k-1; ++i)
        res += a[i];
    res = -res + k * a[n-1];
    printf("%lld\n", res);
    return 0;
}

Python代码:

n, k = [int(x) for x in input().strip().split(" ")]
a = [int(x) for x in input().strip().split(" ")]

S = [sum(a[:i+1]) for i in range(n-1)]
S.sort()
res = -sum(S[:k-1]) + k * sum(a)
print(res)

   转载规则


《昨晚学妹参加了B站秋招笔试,还想考考我?》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 本篇
昨晚学妹参加了B站秋招笔试,还想考考我? 昨晚学妹参加了B站秋招笔试,还想考考我?
学妹昨晚参加了B站的2022届秋招算法笔试,做完给我发来了一道题,想考考我,说挺难的。 我看了两分钟,给她发去了我的思路。然后学妹一眼就看懂了,立马秒过。 那么这道题到底是怎么做的呢? 题目要求将$n$个数切分成$k$块,求每块的序号乘上该
2021-08-26
下一篇 
cuBLAS矩阵乘法性能分析(附代码示例) cuBLAS矩阵乘法性能分析(附代码示例)
使用教程矩阵乘法是神经网络中最基础、最重要的一个运算。在用CUDA实现矩阵乘法时,不需要我们手动写,cuBLAS库提供了现成的矩阵乘法算子,例如cublasGemmEx和cublasLtMatmul。其中后者是轻量级版本,API调用更灵活。
2021-08-24
  目录