美团3.25 前端移动笔试

第一题

小美是一个火车迷。最近她在观察家附近火车站的火车驶入和驶出情况，发现火车驶入和驶出的顺序并不一致。经过小美调查发现，原来这个火车站里面有一个类似于栈的结构

例如可能1号火车驶入了火车站中的休息区s，在驶出之前2号火车驶入了。那么在这种情况下，1号火车需要等待2号火车倒车出去后才能出去(显然被后面驶入的2号火车挡住了，这个休息区s只有一个出入口)。出于好奇，小美统计了近些天的火车驶入驶出情况，开始统计和结束统计时休息区s中均是空的。由于中途疏忽，小美觉得自己好像弄错了几个驶入驶出顺序，想请你帮她验证一下。值得注意的是，小美虽然可能弄错了顺序，但对火车的记录是不重不漏的。

形式化地来形容休息区s， 我们视其为一个容量无限大的空间，假设两列火车i和j同时处于

休息区s中，驶入时刻Tin满足Tin(i)<Tinj),则驶出时间Tout必定满足Tout0i)>Touf0),即，

先进后出。

第一行一个整数T表示数据组数。对每组测试而言: 第一行一个整数n，表示观察到的火车数量。第二行n个整数x1,x2,.,,表示小美记录的火车驶入休息区s的顺序。第三行n个整数y1y2,.….,yn,表示小美记录的火车驶出休息区s的顺序。1≤T≤10,1≤n≤50000,1≤x,i≤n,且(x,)、iy,均为[1,2,3.….n的一个排列，即1-n这n个数在其中不重不漏恰好出现一次。输出描述对每组数据输出-行:如果小美记录的驶入和驶出顺序无法被满足则输出No，否则输出Yes. 输入描述

第一行一个整数T表示数据组数。

对每组测试而言:

第一行一个整数n，表示观察到的火车数量。

第二行n个整数x1,x2,.,,表示小美记录的火车驶入休息区s的顺序。

第三行n个整数y1y2,.….,yn,表示小美记录的火车驶出休息区s的顺序。

1≤T≤10,1≤n≤50000,1≤x,i≤n,且(x,)、iy,均为[1,2,3.….n的一个排列，即1-n这

n个数在其中不重不漏恰好出现一次。

输出描述

对每组数据输出-行:如果小美记录的驶入和驶出顺序无法被满足则输出No，否则

输出Yes.

第二题

小美明天要去春游了。她非常喜欢吃巧克力，希望能够带尽可能多的巧克力在春游的路上吃。她现在有n个巧克力，很巧的是她所有的巧克力都是厚度一样的正方形的巧克力板，这n个巧克力板的边长分别为a1,a2,...,an。因为都是厚度一致的正方形巧克力板，我们认为第 i 个巧克力的重量为。小美现在准备挑选一个合适大小的包来装尽可能多的巧克力板，她十分需要你的帮助来在明天之前准备完成，请你帮帮她。

输入描述:

第一行两个整数n和m，表示小美的巧克力数量和小美的询问数量。

第二行n个整数a1,a2,...,an，表示n块正方形巧克力板的边长。注意你不能将巧克力板进行拆分。

第三行m个整数q1,q2,...,qm，第 i 个整数qi表示询问：如果小美选择一个能装qi重量的包，最多能装多少块巧克力板？（不考虑体积影响，我们认为只要质量满足要求，巧克力板总能塞进包里）

1≤n,m≤50000,1≤ai≤104,1≤qi≤1018

示例：

5 5

1 2 2 4 5

1 3 7 9 15

输出描述:

输出一行m个整数，分别表示每次询问的答案。

示例：

1 1 2 3 3