[堆排序]NOIP2004 合併果子 fruit 堆排序算法(Heap)

 具體的題目和解析的就不再貼出來啦，請看我以前的文章。


【小根堆算法 一：快速排序建堆  0.053s】
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int top;
int A[20000];

int cmp(const void *a,const void *b)
{
    return *((int *)a)-*((int *)b);
}

void init()
{
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
        scanf("%d",&A[i]);
    qsort(A+1,N,sizeof(A[0]),cmp);
    top=N;
    return;
}

void swap(int x,int y)
{
    int tmp;
    tmp=A[x];
    A[x]=A[y];
    A[y]=tmp;
}

void Insert(int x)
{
    A[++top]=x;
    int k=top;
    while(k>1 && A[k]<A[k>>1])
    {
        swap(k,k>>1);
        k=k>>1;
    }
}

void Delete(int x)
{
    int tmp;
    A[x]=A[top--];
    int k=x;
    while(k<<1<=top)
    {
        bool flag=true;
        tmp=k<<1;
        if(tmp+1<=top)
            if (A[tmp]>A[tmp+1])
                tmp++;
        if(A[k]>A[tmp])
        {
            flag=false;
            swap(k,tmp);
        }           
        if(flag)
            break;
        k=tmp;
    }
}

void greedy()
{
    int S=0;
    int T;
   
    while(top>1)
    {
        int tmp=2;
        if(A[2]>A[3] && top>2)
            tmp=3;
        T=A[1]+A[tmp];
        S+=T;
        Delete(1);
        Delete(1);
        Insert(T);
    }
    printf("%d\n",S);
    return;
}

int main()
{
    freopen("fruit.in","r",stdin);
    freopen("fruit.out","w",stdout);
    init();
    greedy();
    return 0;
}
評測結果：
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	352 KB	0
2	正确	10	0.001 s	352 KB	0
3	正确	10	0.001 s	352 KB	0
4	正确	10	0.004 s	352 KB	0
5	正确	10	0.004 s	352 KB	0
6	正确	10	0.009 s	352 KB	0
7	正确	10	0.008 s	352 KB	0
8	正确	10	0.009 s	352 KB	0
9	正确	10	0.008 s	352 KB	0
10	正确	10	0.008 s	352 KB	0

运行完成
运行时间 0.053 s
平均内存使用 352 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!





【小根堆算法二：向下維護建堆 0.037s】
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int top;
int A[20000];

int cmp(const void *a,const void *b)
{
    return *((int *)a)-*((int *)b);
}

void downshift(int i)
{
    int j,x;
    x=A[i];
    j=i<<1;
    while (j<=N)
    {
        if (A[j]>A[j+1] && j+1<=N)
            j++;
        if (x>A[j])
        {
            A[i]=A[j];
            i=j;
            j=j<<1;
        }
        else
            break;
    }
    A[i]=x;
}

void init()
{
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
    {
        scanf("%d",&A[i]);
    }
   
    for (int i=N/2;i>=1;i--)
        downshift(i);
    top=N;
    return;
}

void swap(int x,int y)
{
    int tmp;
    tmp=A[x];
    A[x]=A[y];
    A[y]=tmp;
}

void Insert(int x)
{
    A[++top]=x;
    int k=top;
    while(k>1 && A[k]<A[k>>1])
    {
        swap(k,k>>1);
        k=k>>1;
    }
}

void Delete(int x)
{
    int tmp;
    A[x]=A[top--];
    int k=x;
    while(k<<1<=top)
    {
        bool flag=true;
        tmp=k<<1;
        if(tmp+1<=top)
            if (A[tmp]>A[tmp+1])
                tmp++;
        if(A[k]>A[tmp])
        {
            flag=false;
            swap(k,tmp);
        }           
        if(flag)
            break;
        k=tmp;
    }
}

void greedy()
{
    int S=0;
    int T;
   
    while(top>1)
    {
        int tmp=2;
        if(A[2]>A[3] && top>2)
            tmp=3;
        T=A[1]+A[tmp];
        S+=T;
        Delete(1);
        Delete(1);
        Insert(T);
    }
    printf("%d\n",S);
    return;
}

int main()
{
    freopen("fruit.in","r",stdin);
    freopen("fruit.out","w",stdout);
    init();
    greedy();
    return 0;
}

評測結果：
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	352 KB	0
2	正确	10	0.001 s	352 KB	0
3	正确	10	0.001 s	352 KB	0
4	正确	10	0.003 s	352 KB	0
5	正确	10	0.003 s	352 KB	0
6	正确	10	0.006 s	352 KB	0
7	正确	10	0.006 s	352 KB	0
8	正确	10	0.006 s	352 KB	0
9	正确	10	0.006 s	352 KB	0
10	正确	10	0.006 s	352 KB	0

运行完成
运行时间 0.037 s
平均内存使用 352 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!