校招笔试

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)