#你的秋招简历被谁挂了？# #你认为哪些项目算烂大街？# 

A卷，选择题不做记录，只做编程题记录。编程题有点思考量，最终还是写完了，3/3，希望有面试编程1：    一个数组，每次可以选择一个元素a[i]，拆成两个和为a[i]的正整数x,y    问最少多少次拆分可以让数组最大值不超过最小值的2倍    n<=2e5,1<=a[i]<=1e9解法：    记录最小值mn，把超过2mn的数字都强制拆成2mn，不足保留余数。这样每次拆分代价就是a[i]/(2mn)-1，如果a[i]无法整除2mn需要多拆一次。    复杂度O(n)编程2：    一个数组，每次可以选择两个下标i,j，如果n/i==n/j（下取整），则可以把a[i]和a[j]同时变成gcd(a[i],a[j])    令最终数组和最小    n<=2e5,a[i]<=1e9解法：    不妨令n/i（下取整）相同的元素放在一起考虑，他们之间会相互影响，则最小化元素和，就是把每个元素变成他们的公共gcd，计算公共gcd只需要顺序累计gcd即可。    复杂度O(nloga[i])编程3：    一个数组，每次可以交换两个相邻元素，让数组变成单峰序列，求最小交换次数    n<=5e5,a[i]<=1e9解法：    按数值从小到大考虑。最小的数值肯定是排在序列头或者序列尾，可以发现每次考虑完最小元素，剩余元素就变成了一个规模缩小的子问题。只需要每次看把最小元素放在头所需步骤更少，还是放在尾所需步骤更少。另外还需要考虑相同元素的情况。    先考虑最小元素是单独出现的情况，只需判断元素在原数组里，前面有多少个数字，后面有多少个数字即可。考虑完就把数字从原数组删掉。这里可以用线段树、树状数组、或者提前预处理逆序对也ok    然后是相同数字如何处理，假设有k个相同的最小元素。    不妨考虑其中q个放在队头，p个放在队尾。    很显然我们需要按照这些元素原来的相对顺序，前q个依次放队头，后p个逆序依次放队尾，这样是最优的。    直到这个顺序就可以枚举多少个放队头，这里预处理每个元素移动到队头队尾所需的步骤，然后用前缀和优化即可。    最终总复杂度O(nlogn)