百度笔试0410

最佳优惠

时间限制: 3000MS

内存限制: 589824KB

题目描述:

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

该优重券的使用规则是:

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

比如当你选择数字69时，你可以抵扣的金额为
$69\ast (6+9)=1035$

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

输入描述

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

输出描述

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

样例输入
36

样例输出
36

提示

样例解释1
选取数字为$3$的折扣金额是$3\ast 3=9$,数字为$4$的折扣金额是$4\ast 4=16$,数字为$5$的
折扣金额是$5\ast 5=25$,数字为$6$的折扣金额是$6\ast 6=36$,故最大折扣金额为$36$.

输入样例2
11 31
输出样例2
319

样例解释2
选取数字为$29$的折扣金额是$29\ast (2+9)=319$,可以证明这是手上优惠金额最大的一张优惠券。

static int miniTask(int input) {int out = 0;int t = input;while (t > 0) {out += t % 10;t /= 10;}out = out * input;return out;}static int findMax(int L, int R, int step) {int out = 0;if (step == 1) {for (int i = L; i < R; i++) {out = Math.max(miniTask(i), out);}} else {int left = (L / step + 1) * step - 1;for (; left <= R; left += step) {out = Math.max(out, miniTask(left));}left -= step;out = Math.max(out, findMax(left, R, step / 10));}return out;}static int task1() {Scanner scanner = new Scanner(System.in);int L = scanner.nextInt();int R = scanner.nextInt();int out = Math.max(miniTask(L), miniTask(R));int mark = 1;int dis = R - L;if (dis < 10) {out = Math.max(out, findMax(L, R, mark));} else {while (dis >= 10) {mark *= 10;dis /= 10;}out = Math.max(out, findMax(L, R, mark));}return out;}

玩具士兵

时间限制：3000MS
内存限制：589824KB

题目描述：

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

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

小红的每次操作会选择一个数$k$，将前$k$个士兵按战斗力从大到小排序。

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

输入描述

第一行有两个整数$n、m$（1≤nm≤2×1051≤nm≤2×10^51≤nm≤2×105），分别代表士兵的数量与操作次数。第二行有n个整数h1，h2，……，hnh_1，h_2，……，h_nh1​，h2​，……，hn​（−109≤hj<109-10^9≤h_j<10^9−109≤hj​<109），代表初始状态下从前往后各个士兵的战斗力。

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

输出描述

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

样例输入
4 2
1 2 4 3
2 3
1 2

样例输出
2 4 1 3

思路：如果后一个操作的k大于之前的任何一个操作，则之前的任何一个操作不会影响最终的结果

#输入测试用例

n,m = 4,2
tgt = [1,2,4,3,9,8,0]
ops = [[1,5],[1,7],[2,2],[2,3],[1,2]]

从后向前搜索所有操作，使用curmaxcur_maxcurm​ax记录当前最大的$k$

cur_max = [ops[-1]]

#从后向前，找到对最终结果能产生影响的操作

ops.reverse()
for op in ops:# 如果该操作大于“当前最大的k”，则该记录能对最终结果造成影响if cur_max[-1][1]<op[1]:cur_max.append(op)cur_max.reverse()

#依据curmaxcur_maxcurm​ax记录的操作，对玩具士兵进行操作

for op in cur_max:temp = tgt[:op[1]]temp.sort(reverse=(op[0]!=1))tgt[:op[1]]=tempprint(tgt)

语文教学资源