網頁

2014年2月9日 星期日

UVa 10025 The ? 1 ? 2 ?....? n = k problem

想法:
  可以先將k取絕對值,只考慮正數k,然後假設?都是+,也就是sum = +1+2+3+....+n,然後當sum > k時,將某些'+'變成'-'湊成k,可以發現把'+'變成'-'時,sum都是減掉偶數,例如Example,sum = +1+2+..+5 = 15,要湊成12,這時候把任一個數變號都是減掉偶數,因此奇數(15)減掉偶數不可能變成偶數(12),所以要把sum往上加,直到sum為偶數為止(因為偶數-偶數=偶數)。
  總結:sum = 1+2+3+..+n,如果k為偶數,sum為>=k的最小偶數(偶=偶-偶);如果k為奇數,sum為>=k的最小奇數(奇=奇-偶)。