| ||||||||||
| 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