怎么优化这题不会tle - 编程论坛

#2

pangding2011-09-15 22:34

就用小顶堆的标准算法会超时吗？
如果会的话，那这题感觉就不能用堆算了呀。（而且用其它结构感觉也没什么太多速度优势）

#3

skogt2011-09-17 18:02

回复 2楼 pangding

写出来看看。。

#4

pangding2011-09-17 22:56

是说你连本讲数据结构或者算法的书都没有吗……

#5

pangding2011-09-18 00:53

程序代码：

#include <stdio.h>

#define N 1000
int heap[N];
int top = 0;

void add(int x)
{
    int prt, cld;
    heap[top++] = x;

    for (cld = top-1; (cld-1)/2 >= 0; cld = prt)
    {
        prt = (cld-1)/2;
        if (heap[prt] <= heap[cld]) break;
        heap[top] = heap[cld];
        heap[cld] = heap[prt];
        heap[prt] = heap[top];
    }
}

void del()
{
    int prt, cld;
    if (top == 0)
    {
        printf ("EMPTY\n");
        return;
    }

    heap[top--] = heap[0];

    for (prt = 0; 2*prt+1 <= top; prt = cld)
    {
        cld = 2 * prt + 1;
        if (cld+1 <= top && heap[cld+1] < heap[cld]) ++cld;
        if (heap[top] < heap[cld]) break;
        heap[prt] = heap[cld];
    }
    heap[prt] = heap[top];
}

void query()
{
    if (top == 0)
        printf ("EMPTY\n");
    else
        printf ("%d\n", heap[0]);
}

int main (int argc, const char *argv[])
{

    return 0;
}

得空给你写了一个，main 函数你自己加上唄。
没怎么调试，不敢保证是对的。不过思路你可以借鉴一下。

另外，你可以把你那个 tle 的代码发上来。大家看看是不是有改进的余地，没准改改就能用了呢～

#6

skogt2011-09-18 09:21

回复 5楼 pangding

我好像是直接数组模拟的==，一开始还以为数据宽点会AC==，这个最小堆没怎么写过。。

程序代码：

#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;

int a[50005];

int main()
{
    int n;
    int x;
    scanf("%d",&n);
    string str;
    int num = 0;
    memset(a,0,sizeof(a));
    while(n--){
        cin >> str;
        if(str == "add"){
            scanf("%d",&x);
            a[num++] = x;
            sort(a, a + num);
        }else if(str == "query"){
            if(num == 0)    printf("EMPTY\n");
            else printf("%d\n",a[0]);
        }else if(str == "del"){
            if(num == 0)    printf("EMPTY\n");
            else{
                for(int i = 1,j=0; i < num; i++)
                    a[j++] = a[i];
                num--;
            }
        }

    }
    return 0;
}

#7

玩出来的代码2011-09-18 10:23

你写的这个timeout是必须的，大量的sort，内存copy、、最小堆得操作add,del为O(log(n)),query为O(1)。

#8

pangding2011-09-18 11:26

哦。有的 OJ 不能 c++ 的。如果可以的话，就能直接用 STL 的 push_heap 和 pop_heap 应该就行了。对应 add 和 del。

#9

skogt2011-09-18 19:14

回复 7楼玩出来的代码

en...主要是最小堆从来没写过。。。没办法，只能硬来试试看呃

#10

skogt2011-09-18 19:53

回复 8楼 pangding

没用过这个STL里面的make_heap()之类的，请以这题写一下，学习了。。

#11

skogt2011-09-18 20:34

回复 8楼 pangding

程序代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>

using namespace std;

#define N 50005
int heap[N];
int top = 0;

bool cmp(const int &a,const int &b){
    return a > b;
}
int main ()
{
    int n;
    scanf("%d",&n);
    string name;
    for(int i = 0; i < n; i++){
        cin >> name;
        if(name == "add"){
            //printf("top==%d\n",top);
            int x;
            cin >> x;
            heap[top++]=x;
            make_heap(&heap[0],&heap[top],cmp);
        }
        else if(name == "query"){
            //printf("top==%d\n",top);
            if(top == 0)    printf("empty\n");
            else{
            //    sort_heap(&heap[0],&heap[top-1],cmp);
                printf("%d\n",heap[0]);
            }
        }else if(name == "del"){
            //printf("top==%d\n",top);
            if(top == 0)    printf("empty\n");
            else{
                pop_heap(&heap[0],&heap[top],cmp);
                top--;

            }
        }
    }

    return 0;
}

STL里面的heap函数调用效率不是很高啊。。。虽然简单了，但还是tle了

#12

玩出来的代码2011-09-18 21:23

你每次都make_heap肯定不行了，不是有push_heap的吗，为什么不用
堆建好后，只需要push,pop,query就行了。

#13

skogt2011-09-18 22:45

回复 8楼 pangding

有道理

#14

skogt2011-09-18 22:55

回复 12楼玩出来的代码

直接每次调用push_heap()就行了。。。我水了==