【鏈接】 我是鏈接,點我呀:)
【題意】
在這里輸入題意
【題解】
證明:前i個數一定能湊夠1..sum[i]中的所有數字
i=1時顯然成立。
現在假設i>=2時結論成立
即前i個數字能湊出1..sum[i]
令k=i+1;
現在證明前i+1個數字能湊出1..sum[i+1]
即用前i個數字和數字a[i+1]湊出1..sum[i+1]
現在我們把i+1個數字全都用上。
得到sum[i+1]
現在我們要再得到sum[i]+1,sum[i]+2..sum[i+1]-1
那么我們只要用sum[i+1]減去p就好
設delta = sum[i+1]-sum[i]
則p∈[1..delta-1]
而顯然p是小于等于i的;(因為sum[i+1]-sum[i]-1<=i)
而sum[i]>=i
則說明前i個數字一定能湊夠所有的p即湊夠1..delta-1
那么我們把湊出來的數字從這i+1個數字里面刪掉。
剩下的就是所需求的新湊出來的數字了
則sum[i]+1,sum[i]+2..sum[i+1]-1這些數字都能用前i+1個數字湊出來。
則前i+1個數字能夠湊夠1..sum[i]中的所有數字。
知道這個結論之后。從后往前貪心湊就可以了。
(sum[n]為奇數顯然無解
(選擇sum[n]/2為負數就好
【代碼】
在這里輸入代碼
