推 pigcat1315: = = 我成大的也很低 03/17 21:58
推 h88488848:可能差在遞迴式20分吧 03/17 22:36
推 orzreynold:哪個遞迴式我忘了= = 03/17 22:45
→ DavyBlue:成大考的遞迴?證時間複雜度那題嗎? 03/17 23:14
※ 編輯: DavyBlue 來自: 114.36.211.210 (03/17 23:33)
: 13. 有點不是很懂在幹嘛
針對第13題
這跟今年成大最後一題好像
我的想法是
令兩個array C[0..k-1] D[0..k-1]
C[i]存放數值為i+1的個數
D[j]存放value為1~j+1的個數和
然後只要求D[b-1]-D[a-1]+C[a-1]就會是range[a,b]的數值個數
Algo:
pre-process(int[] a,int[] c,int[] d){
for(int i=0 ; i<n ;i++){
c[a[i]]+=1;
}
for(int j=0 ; j<k ;j++){
if(j==0) d[j] = c[j];
else
d[j]=d[j-1]+c[j];
}
}
getCount(int a,int b){
return d[b-1]-d[a-1]+c[a-1];
}
--
我想說的是 如果我這樣寫沒錯
為啥我成大程設才25分 完全沒道理阿...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.36.211.210