美团算法题真题（技术类9）

前言：

据我了解，美团笔试的算法题是比较简单的，大家要查漏补缺，尽量全部做出来，不然可能很难拿到面试（如果题目简单的话）。

序列问题

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

小美有一个长度为n的序列A，她定义序列中第i个数的prev[i]值为前i-1个数中比A[i]小的最大的值，即(j<i且a[j]<a[i]中最大的a[j])，若不存在这样的数，则prev[i]的值为0。现在她想要你帮忙计算对于所有的i，prev[i]i之和是多少，即Σiprev[i]。

输入描述

第一行是一个整数n表示序列的长度。

接下来一行n个数用空格隔开，第i个数表示A[i]的大小。

输出描述

一行一个整数，表示答案。

输入样例1

5

1 6 3 3 8

输出样例1

39

数据范围和说明

30%的数据保证 n<=20，1<=A[i]<=100。

60%的数据保证 n<=1000，1<=A[i]<=1000。

100%的数据保证 n<=100000，1<=A[i]<=100000。

找数

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

小美和小团在玩游戏。小美将会给出n个大小在1到n之间的整数，然后小美会再告诉小团一个整数k，小团需要找到一个最小的整数x满足以下条件：

l 整数x的大小在1到n之间

l 在小美给出的n个整数中，恰好有k个数比x小

输入描述

第一行是一个数T，表示有T组数据。

对于每组数据：

第一行有两个整数n和k，分别表示小美将会给出n个数以及她给出的整数k。

接下来一行有n个用空格隔开的正整数，表示小美给出的n个正整数。

输出描述

对于每组数据：

如果存在满足要求的数x，第一行先输出“YES”（不含引号），第二行输出数x的值。

如果不存在满足要求的数x，输出“NO”（不含引号）。

输入样例1

2

6 6

1 6 6 2 1 3

6 3

1 6 5 2 2 5

输出样例1

NO

YES

3

数据范围和说明

30%的数据保证 n<=10, 0<=k<=n, T<=10

60%的数据保证 n<=1000, 0<=k<=n, T<=10

100%的数据保证 n<=100000, 0<=k<=n, T<=10