| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1215 人关注过本帖
标题:怎么优化这题不会tle
只看楼主 加入收藏
skogt
Rank: 1
等 级:新手上路
帖 子:14
专家分:3
注 册:2011-5-27
收藏
得分:0 
回复 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了
2011-09-18 20:34
玩出来的代码
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:河南新乡
等 级:贵宾
威 望:11
帖 子:742
专家分:2989
注 册:2009-10-12
收藏
得分:0 
你每次都make_heap肯定不行了,不是有push_heap的吗,为什么不用
堆建好后,只需要push,pop,query就行了。

离恨恰如春草,更行更远还生。
2011-09-18 21:23
skogt
Rank: 1
等 级:新手上路
帖 子:14
专家分:3
注 册:2011-5-27
收藏
得分:0 
回复 8楼 pangding
有道理
2011-09-18 22:45
skogt
Rank: 1
等 级:新手上路
帖 子:14
专家分:3
注 册:2011-5-27
收藏
得分:0 
回复 12楼 玩出来的代码
直接每次调用push_heap()就行了。。。我水了==
2011-09-18 22:55
快速回复:怎么优化这题不会tle
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017371 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved