偷偷拿出一点美团官方真题【技术类 第一期】

声明：总共9期，慢慢发，是去年秋招的，之后春招有新的了，我再弄过来

有问题可以问，看到了就会回复

【技术类 第一期】

找数

时间限制: 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

--------------------

序列问题

时间限制: 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。