百度笔试A卷

第一题 min*2>=max

先找最小值，然后ans+=(nums[i]-1)/(min*2)

例：

1. 最小值为3
2. min*2=6
3. 任何大于6的num最优分解是6+(num-6)
4. 总的分解次数就是(num-1)/6
5. 补充：7实际不能分解为1+6而应该分解为3+4，但是我们不需要单独处理这种情况，只需要知道都是分解一次即可

要用long long，没用20%

第二题 gcd

同一个区间所有数gcd，然后*区间大小，最后所有区间加起来就行

要用long long ，没用0%

第三题 先递增后递减

我过了25，10％单独判断是否有序，15%正常求解

我的想法是

1. 先找到最小的，然后移动到最左或最右（比较一下哪边近）（不用真的移动，直接删除此元素即可）
2. 然后对剩余元素重复此过程

O(n2)时间复杂度，n<=5e5。没想到只能过15%

可以用数组或链表，链表稍好，但写起来比较麻烦。然后有一个做完才想到的优化方案，判断一下最小的元素接下来一位是否相同，这样可以少遍历一次，对于相同元素很多的情况可以节省不少时间。

这个思路优化空间挺有限的，答案应该不是这个思路，但确实想不到其他方案，当然想思路就想了好久。

————————————————————————————————————————————————————————————————————

贴一下大佬解法：

https://www.nowcoder.com/feed/main/detail/2f03cd0f656c42e8b42e668f902cdb7b?sourceSSR=search

有点印象，当时学的时候是说可以逆序对，但也仅限有印象了。