得物秋招 2023.09.12 编程题目与题解

发表于 2023-09-12 更新于 2023-11-11 分类于笔试阅读次数：本文字数： 1.1k 阅读时长 ≈ 1 分钟

1、小A的宝石

小A收集到了$n$颗宝石，第$i$个宝石有其美丽值$a[i]$，小A决定挑出一些宝石带回家，一颗带回家的宝石给小A带来的快乐值与其石头本身的美丽值相等。虽然并不是所有宝石的美丽值都为正数，但是小A还是认为能有收获也是一件很开心的事，故而每带回家$3$颗宝石，小A的快乐值就会加$k$。问小A要如何选择宝石带回家，使得自已能获得的快乐值最高。请输出快乐值的最大值。

输入

第一行包括两个正整数$n,k$，表示收集到的宝石的数量和每带回家$3$颗宝石快乐值的增加量。

第二行包括$n$个整数，表示第$i$颗宝石的美丽值。

$-1000\le a[i]\le 1000,1\le k\le 1000,1\le n\le 100000$

输出

输出能获得的快乐值的最大值

样例

输入：
5 5
1 2 3 4 -6

输出：
15

提示：
带回前三颗宝石能获得(1+2+3+5=11)的快乐值，同时再带回第四颗宝石，总共获得的快乐值为15，这时是能获得的最大的快乐值。

解答

可见，在选择相同数量的宝石的情况下，应该选择美丽值最大的。

因此，我们需要对$a$逆序排序，假设排序后满足$a[1]\ge a[2]\ge \dots\ge a[n]$。

如果我们目前拿起了$i$块石头，那么其快乐值会额外增加$k\cdot \lfloor i/3\rfloor$。

因此，令数组$a$的前缀和为$\displaystyle{s[i]=\sum_{j=1}^i a[j],s[0]=0}$，那么最终答案为

\[\displaystyle{\max_{i=0}^n\{s[i]+k\cdot \lfloor i/3\rfloor\}}\]

代码

n, k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
ans = s = 0
for i in range(n):
    s += a[i]
    ans = max(ans, s + (i + 1) // 3 * k)
print(ans)

2、填充

现在有一个$n\times n$的矩阵，初始全为$1$。

你现在需要将恰好$k$个$1$变为$0$，使得这个矩阵是关于主对角线对称的，并且字典序最小。

关于名词的提示：

主对角线：指矩阵左上角到右下角的对角线

矩阵的字典序：矩阵的字典序比较方式为先比较第一行，如果没有区别再比较第二行，比较第三行等等。对于每一行，从左向右一个一个比较。当遇到第一个不相同的地方，则以这一个位置的大小关系作为矩阵整体的字典序大小关系。

输入

输入包含两个数$n,k$。

$ 1n ,0kn^2$

输出

输出包含一个矩阵，$n$行$n$列，代表你的答案。

样例

解答

按照字典序的定义，我们优先将前面的值尽量变成$0$。因此，我们从上往下遍历每一行。然后从主对角线右侧的每一列进行遍历。

由于这是一个对称矩阵，因此如果要对$a_{i,j}$置$0$，那么也要对$a_{j,i}$置换$0$。如果$i<j$，那么就需要消耗$2$次操作次数，否则只需要消耗$1$次操作次数。

因此，在操作次数足够的情况下，优先选择最上面的行，最右边的列置$0$即可。

代码

n, k = map(int, input().split())
a = [[1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(i, n):
        x = 1 + int(i != j)
        if x <= k:
            k -= x
            a[i][j] = a[j][i] = 0
for u in a:
    print(*u)