出處:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3562
解題策略:
列舉所有區間累加演算法效率為O(n^3),n為100000,一定會逾時(TLE)。
事先累加所有數值,可以降低到O(n^2)也是逾時(TLE)。
列舉右邊界,累加所有正整數為遞增數列,使用二分搜尋找出累加超過S最少個數,演算法效率為O(n*log(n))
因為左右邊界皆為遞增數列,先找到右邊累加超過S,在找尋左邊確定個數,右邊界向右一格,繼續找可行的左邊界,不行就繼續移動右邊界,直到右邊界到最右邊,演算法效率為O(n)
參考程式