这题数据较弱,暴力优化后可AK.
(Tips:老师已经知道了可能要优化数据力）
未优化前代码:20pts
纯暴力时,由于sort()平均复杂度为O(nlogn)O(nlogn)O(nlogn),因此本方法时间复杂度为O(mnlogn)O(mnlogn)O(mnlogn).对于m=n=5∗105m = n = 5 * 10 ^ 5m=n=5∗105,有T≈1.42∗1012T ≈1.42*10^{12}T≈1.42∗1012,会超时。
优化后时间复杂度将为O(mn)O(mn)O(mn),并有剪枝(? 虽然剪枝一般说的是搜索,但是找不到好的形容词了)优化,且本题数据较弱,故能AK.
