2020.4.17
阿里巴巴实习生笔试题
1、输入一个数 n，要输出 n个数，这n个数是 1-n 的排列，
要求满足，
对于排列中 i<k<j，有 ai + aj != 2*ak ；
我的思路是：
对一个存有1-n按顺序排好的数组，
每次从首尾拿，
比如n = 4，
数组-》1 2 3 4
从首部拿 1，
数组-》2 3 4
从尾部拿 4
数组-》2 3
从首部拿 2
数组-》3
从尾部拿 3
输出 1 4 2 3。
样例通过0.0%。。。
不解？？？
之后在小伙伴的悉心分析下，原来 i<k<j 中，i，k，j 是不连续的！！！!
2、在一个有 n 个节点的环形图中，有 n 条无向边，
前 n-1 条边的权值为 第 i 个节点到 第 i+1 个节点的距离，
第 n 条边的权值为第 n 个节点到第 1 个节点的距离，
现有 q 个人，每个人都有各自的起点和终点。
很明显，从起点到终点的路径有两条，默认会走距离小的那条。
n 条边每条边有相同的概率会被切断，
问：每个人从起点到站点的距离变大的概率，对每个人输出对应的概率，用最简分数表示。
输入：
第一行：2个数 n 和 q；
第二行：n个数，代表 n 条边的权值；
其余 q 行，每行 2 个数，为 q 个人对应的起点和终点；
输出：
q 行，每行用最简分数表生，如 1/3。
想着用数组 d[i] 记录第 1 个节点按节点编号的顺序走到第 i 个节点的距离，
第 1 个节点到第 n 个节点的直接距离记为 w，
先得到未切割边时起点 u 到 终点 v 的两个距离为
路径1：按节点编号顺序到达终点的距离 L1 = d[v] - d[u]，路径含 (u-v-1) 条边；
路径2：不按节点编号顺序到达终点的距离 L2 = d[n] - d[v] + d[u] + w，路径含 n-(u-v-1) 条边；
比较 L1 和 L2 的大小。
如果 L1 小，则当切断的边包含在路径1时，从起点到终点的距离会变大，那么最终的概率为 (v - u - 1)/n；
同理，如果 L2 小，则当切断的边在路径2中时，从起点到终点的距离会变大，最终的概率为 (n-u+v+1)/n；
以上是我的思路，并未得到证实。
记一次历时一小时的 0 题笔试体验。
