Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

请问,用平衡树怎么做?

Posted by cotton at 2011-07-18 20:40:49 on Problem 1442
我最近初学STL 写了如下代码
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<set>

const int maxm=200000+5;
using namespace std;
multiset<int> data;
typedef struct the_Order{
    int add,get;
};
the_Order ord[maxm];
class toget{
    private:
        int count;
        set<int>::iterator toput;
        int i;
    public:
        toget()
        {
            count=0;
        }
        void output()
        {
            ++count;
            toput=data.begin();
            for (i=1;i<count;++i) ++toput;
            printf("%d\n",*toput);
        }
        inline void add(int a)
        {
            data.insert(a);
        }
};
toget work;
int main()
{

    int i,j,k,u, m,n;
    scanf("%d%d",&m,&n);
    
    for (i=1;i<=m;++i) 
    {
        scanf("%d",&ord[i].add);
    }
    for (i=1;i<=n;++i)
    {
        scanf("%d",&u);
        ++ord[u].get;
    }
    for (i=1;i<=m;++i)
    {
        work.add(ord[i].add);
        while (ord[i].get)
        {
            --ord[i].get;
            work.output();
        }
    }

    return 0;
}
结果就TLE了。请问,正确的做法是什么?多谢!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator