小米

小米

90分钟：24道单选+1道双选+2道编程

第一道：背包问题

题目描述： 小明正在整理他的玩具，他遇到了一道有趣的装箱问题：他有一个容量为N的箱子，并且有n个大小为a[i]的玩具。除了这n个玩具外，还有c个大小均为1的填充物，它们是小明参加各种活动的纪念品，正好可以拿来填充缝隙。他的任务是确定是否可以选其中一些玩具（填充物也包含在内）放入箱子中，恰好装满箱子，而不留下任何空隙。当然，他也可以选择全部用填充物来填满整个箱子（如果填充物足够多的话），也即装满一箱纪念品，小明也觉得很棒！

输入描述 第一行1个整数T，表示数据组数。

对于每组数据：

第一行包含三个整数N和n和c，分别表示箱子的容量和玩具的数量以及填充物数量。

第二行包含n个整数a[1],a[2],...,a[n]，分别表示这N个玩具的大小。

1≤T≤100, 1≤n≤500, 1≤N,c,a[i]≤1000

输出描述 输出T行分别表示每组数据答案。

对每组数据，输出一行，如果可以恰好装满箱子，输出 YES；否则，输出 NO。

样例输入： 2 10 4 1 2 3 5 7 10 1 3 6

样例输出： YES NO

提示 对第一组样例：

箱子的容量是 10，玩具的大小分别为 2、3、5 和 7。 其中一种可行的方法为：玩具 2、3 和 5 加起来正好是 10，所以可以恰好装满箱子，因此输出 YES。

对第二组样例：

只有一个玩具，大小为6，三个大小为1的填充物，全放进去也只有9的大小，无法填满。

第二道

请使用Java编程解决下面问题 题目描述： 小明喜欢解决各种数学难题。一天，他遇到了一道有趣的题目：他需要帮助他的朋友们完成一个排序任务。小明得到两个长度为 n 的数组a[]和b[]。他可以在两个数组对应位置进行交换，即选定一个位置i，交换a[i]和b[i]。他可以进行任意次交换（包括0次），他想知道按最优策略来是否可以达成让至少一个数组，a[]或者b[]，变得有序。有序即数组单调不减（升序）或者单调不增（降序）均可。

形式化地，给定两个长度为n的数组a[]和b[]。你可以任选一个位置i交换a[i]和b[i]，可以进行任意多次这样的操作。你的目标是判断是否能够通过这些操作使得至少一个数组变得有序（升序或降序）。

输入描述 第一行一个整数T，表示数据组数。

对于每组数据：

第一行包含一个整数n，表示数组的长度。

第二行包含n个整数a1,a2,...,an。

第三行包含n个整数b1,b2,...,bn。

1≤T≤100，1≤n≤10000，1≤ai,bi≤10000。

输出描述 输出T行分别表示每组数据答案。

对每组数据，如果能够通过交换操作使至少一个数组变得有序，输出 YES；否则，输出 NO。

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

样例输出 YES NO

提示 第一组数据：

在这个样例中，其中一种可行的方法为：通过交换第2、3、4个位置，我们可以使数组 a变成升序：1 2 3 4 4

第二组数据：

无论如何都无法让任何一个数组变得有序