推 seanptt:我的想法也跟你一樣，不過我在sum的時候有array記錄下來 01/20 15:35
→ seanptt:這樣之後就不用再累加一次，直接判斷 01/20 15:36
※ 引述《privatewind (傷神客)》之銘言：
: ※ 引述《assassin88 (魚躍龍門)》之銘言：
: : 題目：http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_96_01.pdf
: : 想請問一下第七題，不知道這一題該怎麼作答比較好呢？
: : 不是很懂他的題意 XDD
: : 麻煩解答了~thx
: 假設x陣列代表每一個partition, n為元素個數 如:
: x[0] x[1] x[2] x[3] x[4]
: 100 200 300 400 500
: 建立一個A陣列
: A[i]=x[0]+x[1]+...+x[i]
: 對x而言, 可以有0~ i-1種分割點
: x[0] | x[1] x[2] x[3] x[4]
: x[0] x[1] | x[2] x[3] x[4]
: x[0] x[1] x[2] | x[3] x[4]
: x[0] x[1] x[2] x[3] | x[4]
: D[i]代表x[0]~x[i]與x[i+1]~x[n-1] partition的difference
: D[i]=| A[i] - (A[n-1]-A[i])|
: D[i]=| A[n-1] - 2A[i] |
: 一樣用一個for loop 解決。
這題我的做法不太一樣...
想請大家幫忙看一下
我的作法是先求整體和,除以2為中間值part(兩邊和恰為part為理想)
從第一個數字開始累加,等到累加超過part時
假設最後加入的是第a個數字
設目前的累加值為x的話,比較x跟x-a哪個誰跟part的差比較小
就可知道怎麼分兩邊了
main(1,n,k){
for i = 1 to n
sum = sum + number[i]
part = sum/k
for i = 1 to k-1{
int x = 0
a1=1
while( x<part & ai<= n-k+i){
x=x+number[ai]
ai=ai+1}
if (x-part > (x-number[ai-1]) - part)
ai = ai-2;
else
ai = ai-1
a[i+1] = ai + 1
return ai;
}
}
(a)題來說,k=2
第一部分的for loop= O(n)
第二部分的while loop = O(n) 最多跑n-1次
所以整體的time=O(n)
(c)
第一部分的for loop= O(n)
第二部分的話大約是 O(k*n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.237.182
※ 編輯: genius945 來自: 114.27.237.182 (12/31 20:25)