题解

532 条题解

  • 0
    @ 2006-08-15 18:13:06

    用哈夫曼树的算法.....

    编译通过...

    ├ 测试数据 01:运行超时...

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 119ms

    ├ 测试数据 06:答案正确... 619ms

    ├ 测试数据 07:运行超时...

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行超时...

    再来一个heap的...

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    差距咋这大呢...

  • 0
    @ 2006-07-27 21:24:35

    用堆排

    不用时间就过了

  • 0
    @ 2006-05-26 22:20:55

    贪心算法--选取质量最小的两堆将它们合并

    每次寻找最小值时需要O(n)的时间,总得时间复杂度是O(n^2)!!

    优化的时候就想起了小根堆!(用WinnerTree偶也不管).所以寻找是就降到了O(log2n).

    总得复杂度:

    时间:O(nlog2n)

    空间:O(n)

  • 0
    @ 2006-09-29 13:01:32

    O(n)的算法如下:

    先把原来的果子排序(当然用桶排,因为每堆重量在1..20000内)

    开两个队列

    第一个存原来的(可以在排序的过程中直接存进去)

    第二个存之后的(每次合并的结果)

    显然 第一个队列由于经过了排序 肯定是递增的

    然后,每次从两个队列的队首取出比较小的那个数 取两次

    加起来塞到第二个队列的末尾

    第二个队列由于是每次取最小的两个求和再放进去 也肯定是递增的

    直到两个队列加起来只有1个元素为止 那个就是答案

    显然排序是常数时间,而两个队列的长度差不多 因此总体是O(n)的算法

    ---|---|---|---|---|---|---|---|---|---|---|---|-

    To YJ狗狗: 只用1个队列可以吗? 请说明做法

    To hbxfwz: 测试数据中确实做到了每堆

  • -1
    @ 2020-02-09 11:08:58

    #include <cstdio>
    #include <queue>
    #define int long long
    using namespace std;
    queue <int> q1;
    queue <int> q2;
    int to[100005];
    void read(int &x){
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;}
    signed main() {
    int n;read(n);
    for (int i = 1; i <= n; ++i) {
    int a;read(a);to[a]++;}
    for (int i = 1; i <= 100000; ++i) {
    while(to[i]) {to[i] --;q1.push(i);}}
    int ans=0;
    for (int i=1;i<n;++i){
    int x,y;
    if((q1.front()<q2.front()&&!q1.empty())||q2.empty()){
    x=q1.front();q1.pop();}
    else{x=q2.front();q2.pop();}
    if((q1.front()<q2.front()&&!q1.empty())||q2.empty()){
    y=q1.front();q1.pop();}
    else{y=q2.front();q2.pop();}
    ans+=x+y;q2.push(x + y);}
    printf("%lld" ,ans);
    return 0;}

  • -1
    @ 2017-09-13 22:58:26

    就是一个huffman编码的问题,最小的次数最多,最大的次数最少。
    这题用优先队列可以做到nlogn,因为队列找出最小和次小只要logn
    当然可以用线性查找的方式,最后就是n平方了,不过也可以AC。

  • -1
    @ 2017-09-13 22:42:25

    这题和POJ3253几乎一模一样,注意POJ那边用long long。

  • -1
    @ 2017-08-01 14:48:01

    麻烦的用了优先队列,不过长度可以忍受了。

    #include<cstdio>
    #include<iostream>
    #include<queue>
    using namespace std;
    priority_queue<int> que;
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=0,x;i<n;++i)
        {
            scanf("%d",&x);
            que.push(-x);
        }
        int ans=0;
        for(int i=1,tmp;i<n;++i)
        {
            tmp=que.top();
            ans-=que.top();
            que.pop();
            tmp+=que.top();
            ans-=que.top();
            que.pop();
            que.push(tmp);
        }
        cout<<ans<<endl;
        return 0;
    }
    
  • -1
    @ 2017-07-24 19:36:37

    优先队列比较快
    cpp
    #include<bits/stdc++.h>
    using namespace std;
    struct cmp{
    bool operator()(int a,int b){
    return a>b;
    }
    };
    priority_queue<int,vector<int >,cmp> a;
    int main(){
    int n,sum=0,num;
    cin>>n;
    for(int i=0;i<n;i++){
    cin>>num;
    a.push(num);
    }
    if(a.size()==1){
    cout<<a.top()<<endl;
    return 0;
    }
    while(a.size()>1){
    int temp1,temp2;
    temp1 = a.top();
    a.pop();
    temp2 = a.top();
    a.pop();
    //cout<<temp1<<" "<<temp2<<endl;
    sum+=(temp1+temp2);
    a.push(temp1+temp2);
    }
    cout<<sum<<endl;
    return 0;
    }

    • @ 2017-07-29 21:44:22

      握个手

  • -1
    @ 2017-07-21 21:46:04

    二叉堆
    const maxn=30000;
    var heap:array[1..maxn] of longint;
    ans,n,len,a,b,i,tmp:longint;

    procedure put(x:longint);
    var fa,son,tmp:longint;
    begin
    len:=len+1;
    heap[len]:=x;
    son:=len;
    while (son<>1)and(heap[son div 2]>heap[son]) do
    begin
    tmp:=heap[son div 2];
    heap[son div 2]:=heap[son];
    heap[son]:=tmp;
    son:=son div 2;
    end;
    end;
    function get:longint;
    var fa,son,tmp:longint;
    stop:boolean;
    begin
    get:=heap[1];
    heap[1]:=heap[len];
    len:=len-1;
    fa:=1; stop:=false;
    while ((fa*2<=len)or(fa*2+1<=len))and(not stop) do
    begin
    if (fa*2+1>len)or(heap[fa*2]<heap[fa*2+1])
    then son:=fa*2
    else son:=fa*2+1;
    if heap[fa]>heap[son]
    then begin
    tmp:=heap[fa];
    heap[fa]:=heap[son];
    heap[son]:=tmp;
    fa:=son;
    end
    else stop:=true;
    end;
    end;
    begin
    len:=0;
    read(n);
    for i:=1 to n do
    begin
    read(tmp);
    put(tmp);
    end;
    ans:=0;
    for i:=1 to n-1 do
    begin
    a:=get;
    b:=get;
    ans:=ans+a+b;
    put(a+b);
    end;
    writeln(ans);
    end.

  • -1
    @ 2017-06-23 20:46:58

    呵呵呵,一遍过了,水题,pascal堆 都没什么其他操作了。。。。。
    var h:array[0..30000]of longint;
    j,n,i,len,x,a,b:longint;
    ans:int64;
    procedure put(x:longint);
    var fa,son,t:longint;
    begin
    len:=len+1; h[len]:=x; son:=len;
    while (son<>1)and(h[son div 2]>h[son]) do
    begin
    t:=h[son div 2];h[son div 2]:=h[son]; h[son]:=t;
    son:=son div 2;
    end;
    end;
    function get:longint;
    var fa,s,t:longint;
    begin
    get:=h[1]; h[1]:=h[len]; len:=len-1; fa:=1;
    while fa*2<=len do
    begin
    if (fa*2+1>len)or(h[fa*2+1]>h[fa*2]) then s:=fa*2
    else s:=fa*2+1;
    if h[fa]>h[s] then
    begin
    t:=h[fa];
    h[fa]:=h[s];
    h[s]:=t;
    fa:=s;
    end
    else break;
    end;
    end;
    begin
    readln(n); len:=0;
    for i:=1 to n do
    begin
    read(x); put(x);
    end;
    for i:=1 to n-1 do
    begin a:=get; b:=get; ans:=ans+a+b;put(a+b); end;
    write(ans);
    end.

  • -1
    @ 2016-08-08 15:47:33

    优先队列
    单调队列 都可以用

信息

ID
1097
难度
6
分类
贪心 点击显示
标签
递交数
23854
已通过
6310
通过率
26%
被复制
40
上传者