2010年3月18日 星期四

UVa 10125 Sumsets

解題策略

這題的解法很直接,要找d=a+b+c
用四層迴圈下去跑a,b,c,d就好了 XDDDD

我犯了幾個錯誤
  1. 要找最大符合d (意思是數列中可能出現好幾個符合要求的解),所以迴圈應該由最大元素往下找,第一個找到的解就是答案,我一開始由最小元素往上遞增尋找,拿了WA。
  2. 沒找到解就回傳0,殊不知0也有可能是解: 0 = -5 + 3 + 2,這裡也吃了一個WA,所以我後來改回傳 INT_MAX 作為無解。
這題有負值,所以 -5 = -10 + -2 + 7 ,這樣算一組合法的解。
是比較需要小心的地方。

官網論壇上的(a+b)=(d-c)法,方法複雜很多,卻沒有比較快。