小米嵌入式软件实习笔试编程题2

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

点赞&&评论mark超50，附上答案

移山

天帝被愚公的诚心感动，命令手下的仙人帮助移山。

然而仙人的法术也是有局限性的，山势连绵起伏，法术并不能直接把山移走。每次施法，可以把一段连续区域的山头移走相同高度。现在愚公想知道什么时候会有至少一个山头高度小于等于0。

给出一个长度为n的数组a1,……,an，和m表示山头的高度和可以施法的次数，每次施法还会给出左右端点L,R,和高度h，表示将aL…,aR,依次减去h。问在哪次操作之后存在一个ai≤0?(数据保证这样的时刻存在。)

输入描述

第一行两个数n和m，表示山头数量和施法次数。

第二行n个数，分别表示第a1,…,an，即第一个山头到第n个山头的高度。

接下来m行，每行三个数L,R,h，表示一次施法的具体参数。

1≤n,m≤10的5次方,1≤h,ai≤10的9次方,1≤L≤R≤n，均为整数

输出描述

输出一个整数，表示答案。数据保证答案存在。

样例输入

5 4

6 5 3 4 6

1 3 2

4 4 2

3 5 1

1 5 6

样例输出

3

提示

第一次操作之后山头变成4 3 1 4 6

第二次操作之后山头变成4 3 1 2 6

第三次操作之后山头变成4 3 0 1 5

其中第三个山头高度小于等于了0，可见，在第三次施法之后有一个山头的高度变成了0

排队选人

小D是一名老师，他想选出一些同学参加一个团体比赛。总共有n个同学，每个同学有一个能力值x和一个合作值y，小D将这些同学排成一排。

选人的规则如下:小D将选择一排中连续的k个同学参加比赛，而且为了保证比赛成绩，这k个同学的能力值不能小于a合作值不能小于b。小D想知道总共有多少种可能的选人方案

输入描述

第一行四个正整数n，k，a，b。

第二行n个通过空格隔开的正整数表示一排n个同学的能力值。

第二行n个通过空格隔开的正整数表示一排n个同学的合作值。

输出描述

输出一个非负整数表示选人方案数。

样例输入

10 2 2 4

2 2 9 1 8 1 6 1 7 7

4 8 5 1 9 4 1 3 9 4

样例输出

3

提示

有选择第1,2两个人，第2，3两个人，第9，10两个人三种方案。n<= 80000，保证k<=n 且 x,y,a,b<=100000