公司：百度

岗位：算法

笔试平台：赛码

考试时长：120钟

试卷总分：100分

考试题型：单选 30 道（60分），编程 3 道（40分）

时间：2023-04-10 19:00-21:00

单选题

C++/Java、Linux、概率、数据结构、机器学习

编程题

最佳优惠

描述

现在给你一张优惠券。优惠券上有两个正整数L和R。

该优惠券的使用规则是：

你可以任意选取一个位于[L, R]之间的正整数（不妨令其为x），抵扣 x 和 x 各个数位上的数字之和的乘积的金额。

比如当你选择数字69时，你可以抵扣的金额为

69 * (6 + 9) = 1035

现在询问你最大可以利用手中这张优惠券抵扣多少金额？

输入描述

一行，给出两个整数 L, R以空格隔开，代表手中优惠券上的数。

1 ≤ L ≤ R ≤ 1e5

输出描述

输出一行，代表最大优惠金额。

示例

样例输入

3 6

样例输出

36

样例解释1

选取数字为 3 的折扣金额是3*3=9，数字为 4 的折扣金额是4*4=16，数字为 5 的折扣金额是5*5=25，数字为 6 的折扣金额是6*6=36，故最大折扣金额为36。

输入样例2

11 31

输出样例2

319

样例解释2

选取数字为 29 的折扣金额是29 * (2+9)=319，可以证明这是手上优惠金额最大的一张优惠券。

思路

遍历，保留最大值

代码

L, R = map(int, input().split())
ans = 0
for i in range(L, R+1):
    cur = i * sum([int(j) for j in str(i)])
    ans = max(ans, cur)
print(ans)

玩具士兵

描述

小明买了一些玩具士兵，他邀请小红一起玩。他总共有n个士兵，刚开始时，这n个士兵被排成一列，第i个士兵的战斗力为h_i。然后小明和小红开始给它们排序。

二人总共进行了m次操作。小明的每次操作会选择一个数k，将前k个士兵按战斗力从小到大排序。小红的每次操作会选择一个数k，将前k个士兵按战斗力从大到小排序。

请问所有操作结束后从前往后每个士兵的战斗力是多少？

输入描述

第一行有两个整数n、m（1≤n,m≤2x10⁵），分别代表士兵的数量与操作次数。

第二行有n个整数h₁,h₂,……,h_n（-10⁹≤h_i≤10⁹），代表初始状态下从前往后各个士兵的战斗力。

接下来m行按顺序给出所有操作，每行有两个整数t、k（1≤t≤2，1≤k≤n），t=1代表是小明的操作，否则是小红的操作，k代表对前k个士兵进行排序。

输出描述

输出n个整数，代表所有操作结束后从前往后每个士兵的战斗力。

示例

样例输入

4 2

1 2 4 3

2 3

1 2

样例输出

2 4 1 3

思路

单调栈：如果一个操作的k如果大于等于它之前操作的k，那么之前的操作可以忽略

代码

n, m = map(int, input().split())
h = list(map(int, input().split()))
stack, ans = [], []
for _ in range(m):
    t, k = map(int, input().split())
    while stack and stack[-1][-1] <= k:
        stack.pop()
    stack.append((t, k))

stack.append((0, 0))
maxk, l, r = stack[0][1], 0, -1
lst = sorted(h[:maxk])
for i in range(len(stack) - 1):
    length = stack[i][1] - stack[i + 1][1]
    if stack[i][0] == 1:
        ans.extend(lst[r:r - length:-1])
        r -= length
    elif stack[i][0] == 2:
        ans.extend(lst[l:l + length])
        l += length

ans = ans[::-1] + h[maxk:]
print(*ans)