Standard Solution.

第一部分

上述代码的最坏时间复杂度是 $O(nT \log n)$。

第二部分

为了证明中间的小猪不会出现左右往复移动而使时间复杂度达到 $O(n^2T)$ 的情况，我们考虑把场上所有的小猪从左向右平分成三分，分别记为 $A,B,C$。

根据题意，在 $A,B,C$ 中都至少有一只小猪还没下桥的情况下，$A$ 中的小猪总会向左移动，而 $C$ 中的小猪总会向左移动。$\dfrac{T}{2}$ 秒后，$A$ 中任意一只小猪和 $C$ 中任意一只小猪之间的距离将不小于 $T$，因此它们之间一定有一组全部下桥了。

由上可知，时间每过去 $\dfrac{T}{2}$ 秒，桥上小猪的数量都将至少减少 $\dfrac{1}{3}$，即剩下原来的 $\dfrac{2}{3}$ 或更少。因此，整个过程最多持续 $\dfrac{T}{2} \cdot \log _{\frac{3}{2}} n=O(T \log n)$ 秒。

阅读程序可知，它 while 循环内程序的时间复杂度为 $O(n)$，而 while 循环每执行一次相当于时间流逝一秒，因此 while 循环最多会执行 $O(T \log n)$ 次。

综上，上述代码的时间复杂度不高于 $O(nT \log n)$。

第三部分

只要让 $T$ 远大于 $n$（此时可以忽略 $n$ 对小猪位置的影响），且 $T,n$ 足够大，将 $n$ 只小猪都放在 $\dfrac{T}{3}$ 位置（时间每过去 $\dfrac{T}{3}$ 秒，桥上小猪的数量都将减少 $\dfrac{1}{2}$），即可使上述代码的时间复杂度退化到 $O(nT \log n)$。

例如：

• $n=10^6$。
• $T=3 \times 10^{18}$。
• $a_i=10^{18}+i$。