Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:为什么自己写的堆排序超出内存??In Reply To:为什么自己写的堆排序超出内存?? Posted by:sdau_085111 at 2013-04-04 19:58:32 > #include <stdio.h> > > int n1,n2,n; > > enum{ > MAX=5000001, > }; > > int data[MAX]; > > void HeapAdjust_MAX(int n,int target) > { > int nChild; > int nTemp; > nTemp = data[target]; > > while(2 * target <= n) > { > nChild = 2 * target; > if(nChild + 1 <= n && data[nChild] < data[nChild + 1]) > { > nChild++;//指向较大的孩子节点 > } > if(nTemp < data[nChild]) > { > data[target] = data[nChild]; > target = nChild; > } > else break; > } > data[target] = nTemp; > } > void HeapAdjust_MIN(int n,int target) > { > int nChild; > int nTemp; > nTemp = data[target]; > > while(2 * target <= n) > { > nChild = 2 * target; > if(nChild + 1 <= n && data[nChild] > data[nChild + 1]) > { > nChild++; > } > if(nTemp > data[nChild]) > { > data[target] = data[nChild]; > target = nChild; > } > else break; > } > data[target] = nTemp; > > } > > int tmp; > static void inline swap(int x,int y) > { > > tmp = data[x]; > data[x] = data[y]; > data[y] = tmp; > } > void HeapSort_MAX(int n,int cnt) > { > int i; > //先对队列进行大顶堆排序 > for(i = n/2;i >= 1;--i) > HeapAdjust_MAX(n,i); > for(i = n;i >= n - cnt;--i) > { > swap(i,1); > HeapAdjust_MAX(i - 1,1); > } > } > void HeapSort_MIN(int n,int cnt) > { > int i; > for(i = n/2;i >= 1;--i) > HeapAdjust_MIN(n,i); > for(i = n;i >= n - cnt;--i) > { > swap(i,1); > HeapAdjust_MIN(i - 1,1); > } > } > > > int main() > { > int i; > double ans; > long long sum; > freopen("input","r",stdin); > while(scanf("%d %d %d",&n1,&n2,&n)) > { > sum = 0; > if(n1 == 0 || n2 == 0 || n == 0) break; > for(i = 1;i <= n;++i) > { > scanf("%d",&data[i]); > sum += data[i]; > } > HeapSort_MAX(n,n1);//按大顶堆,队列后部分有序 > HeapSort_MIN(n - n1,n2); > for(i = n;i > n - n1 -n2;--i) > sum -= data[i]; > ans = (sum * 1.0)/(double)(n - n1 - n2); > printf("%f\n",ans); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator