网易互娱雷火事业群笔试-游戏研发工程师（第二批）
时长:120分钟 总分:100分
207浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 6 |
矩形排序
排序规则：
面积小的矩形排在面积大的矩形前面
面积相同的矩形，按照宽高比排序，宽高比大的矩形排在宽高比小的矩形前面
宽高比的定义为 min(W/H, H/W)
面积和宽高比都相同的矩形，按照宽排序，宽度更小的矩形排在宽度更大的矩形前面
输入描述： 每组输入两行输入
第一行是一个整数N （0 < N <= 100)
第二行是2*N个整数，分别是每个矩形的宽W和高H，(0 < W,H <= 100)输入样例： 2 2 2 1 1 输出描述： 每组数据输出一行，2*N个整数，分别是排序后的每个矩形的宽W和高H输出样例 1 1 2 2
三角网格
如果一个三角网格可以展开成平面图，这称这个三角网格为平面三角网格，在平面三角网格中，单个三角形的顶点可以有顺时针或者逆时针两种排列，代表了三角形两种不同的朝向。
给定一个N个顶点，M个三角形组成的平面连通三角网格，需要你调整所有三角形索引的顶点顺序，使得所有三角形都和输入的第一个三角形具有相同的朝向，并且在每个三角形内部，序号最小的顶点放在首位。
输入描述： 第一行，两个整数N，M 表示有N个顶点和M个三角形 (3<=N<=400, 1<=M<800)
接下来M行，每行三个数字Ai, Bi, Ci(1<=Ai<=N, 1<=Bi<=N, 1<Ci<=N)，表示第i个三角形的顶点序号输入样例： 6 4 3 2 4 1 3 2 3 6 5 5 3 4 输出描述： 输出M行，每行三个数字，表示调整后的三角形顶点索引，输出的三角形顺序需要和输入保持一致。输出样例 2 4 3 1 2 3 3 5 6 3 4 5
钱老板赶工
请你帮钱老板安排一下完成工作的顺序，以减少总的工作推迟时间。
输入描述： 第一行包含一个正整数 n(1<=n<=20)，表示工作数量。
接下来 n 行，每行包含两个整数，分别表示第 i 项工作的 deadline 和 cost。输入样例： 3 3 3 8 1 3 2 输出描述： 一个数字，表示钱老板最少需要推迟几天才能完成所有工作。输出样例 2
最简分数
2/3, 1/10, 99/100 等等都是最简分数
而
2/4, 5/10, 20/30 等等都不是最简分数
对于任意一个正整数N，以N为分母并以小于等于N的正整数作为分子的分数都有N个
例如，当N=6时，一共有以下6个分数：
1/6, 2/6, 3/6, 4/6, 5/6, 6/6
其中的最简分数有两个，分别是：
1/6, 5/6
我们定义一个叫做“最简分数比”的函数F，这个函数的定义是：
F(x) = (以x为分母并以小于等于x的正整数作为分子的最简分数个数) / x
例如，F(6) = 2/6 ~= 0.333333
在这个问题中，只有一个输入数据N，请计算出所有小于等于N的正整数中，最小的F(n)数值，换句话说，对1到N的所有正整数x都计算F(x)并找出这N个F值中的最小值Fmin
输入描述： 一个正整数 N (1 <= N <= 1000000000)输入样例： 10 输出描述： 一个小数Fmin，输出请四舍五入到小数点后6位输出样例 0.333333
小军砌墙
小军接到一项工作，要用红色和绿色两种砖块建一面宽度W高度H的墙
小军只有以下两种砖块可以用：
红色砖块宽度2，高度1
绿色砖块宽度3，高度1
每种砖块只能按照以上的横向摆放，不能竖起来
横向两块方块之间是有缝的，因此为了让建好墙更稳固，小军会避免在任意相邻的两行间，除了左右两侧以外，出现任何上下对齐的砖缝，请参看下图：
给定一面墙的宽度和高度后，请帮小军计算在以上规则允许的前提下，一共有多少种不同的建墙方式
文本编辑器
先介绍一下光标(上图中最左边的是编辑器显示的行号，用来展示用，并不是文本真正的内容，请忽略)：
1.该编辑器里的光标是类似vi编辑器里命令模式那样，停留在一个字符上方，而不是字符与字符之间。
2.编辑器文本为空的时候（初始时，或者把内容全部删除以后），会显示一个空行，光标停留在那行行首（如图1）。此时执行o命令的话，在下方插入一行（如图2）。
再介绍一下撤销（undo）和重做(redo)命令：
1.编辑器的undo和redo操作跟vi编辑器的一样，是一个基于栈式的撤销功能。每当玩家输入一个命令的时候，如果可撤销的话（见第二条），就该操作压进Undo栈里，栈的大小为无限大，允许撤销全部的操作。
2.只有真正改变编辑器内文本的命令才会进入Undo栈，比如g命令，以及未对文本发生修改的d命令，还有undo、redo命令本身都是不可撤销的，即不会进入Undo栈。
3.当执行undo命令的时候，如果Undo栈里有元素，则从栈顶弹出最后一个命令，撤销掉该命令，光标回到执行该命令前的位置，并且将命令压入Redo栈里。
4.当执行redo命令的时候，如果Redo栈里有元素，则从栈顶弹出最后一个被撤销的命令，重新执行该命令，光标回到执行该命令后的位置，并且将命令重新压入Undo栈里。
5.当执行undo或redo命令的时候，如果相应的栈里没有元素，则不进行任何操作，忽略该命令。
6.当执行任何输入的命令的时候，都会清空Redo栈，即用undo撤销一个命令C的时候，再执行输入的其他命令以后，则不能再用redo功能重做上一次撤销的命令C。
完整的命令列表为：
g x y： 移动光标命令，将光标移动到第x行，第y列上方。当x超过总行数时，则为最后一行。当y超过该行列数的时候，则为最后一列。
i str：在光标所在字符前插入str这句话，光标最终会停留在这句话的最后一个字符上。注意，str必定不为空，但是里面可能包含空格。
a str：在光标所在字符后插入str这句话，其他同上。
o str：在光标所在行的下面另起一新行插入str这句话，其他同上。
dd：删除光标所在行，光标最终会停留在下一行的首字符上。如果删除的是最后一行，则停留在最后一行的首字符上。
d n：从光标所在位置开始，往右删除n个字符（输入保证n>0），最多只会删除到行尾，不会跨过当前行。光标最终停留在删除以后的下一个字符位置上。
undo：撤销上一个对文本发生改动的命令，光标也回到上一个命令执行前所在的位置。如果没命令可以撤销，则什么都不做。
redo：重新执行上一个撤销的命令，光标也回到上一个命令执行后所在的位置。如果没有已经撤销的命令，则什么都不做。注意，如果undo了一个命令，再执行新的命令，则也不能redo。
其中命令名字与参数、参数与参数中间都是用一个空格分割
下图为测试用例例子里的的编辑器里的展示
输入的每一行为一个命令，请处理到输入结束，输入最多不超过1000行，且每行均为合法的命令
输入保证每一行输入的最大字符数不超过1000个字符，且只包含英文、数字和空格输入样例： i abcdef o abcd g 1 10 a abcdef d 4 undo redo dd dd dd a hello world 输出描述： 请输出编辑器打开以后（初始状态），执行完输入命令以后，最后显示的文本输出样例 hello world
