O(NlogN) algorithm with segment tree


  • 0
    S

    oh ,I realised that using a heap is a better solution than this. so just ignore my solution :)


    first you can define an array pair<int,int> q[],to save the p[i] (Profits)and c[i] (Capital).then sort the array q with the q.second(Capital) in the ascending order.
    the by p[i]=q[i].first and c[i]=q[i].second ,we get the new p[] and c[].which c[] is in the ascending order.
    my algorithm is :
    1.each time,select the project with the max profit from all the projects that you can choose,which means the capital of the project <=W
    2.then update W,W+=the profit you get
    3.go to 1
    do these steps k times and then return W.
    now using a segment tree.val[i] means the max value of a interval,and pos[i] means the corresponding index in the array c.
    in the step 1,
    you can get the valid project interval by uper_bound() O(lgn)
    then query in the segment tree O(lgn)
    then update the value you chose(to remove it logically) O(lgn)
    so when you do it k times ,the time complexity is O(klgn)
    because there is a sort before this ,so at last ,the time complexity is O(nlgn)

    #define lson id<<1
    #define rson id<<1|1
    #define maxn 50010
    int val[4*maxn+5],pos[4*maxn+5];
    pair<int,int> q[maxn];
    int max(int a,int b)
    {
        return a>b?a:b;
    }
    int min(int a,int b)
    {
        return a<b?a:b;
    }
    void pushup(int id)
    {
        val[id]=max(val[lson],val[rson]);
        if(val[id]==val[lson]) pos[id]=pos[lson];
        else pos[id]=pos[rson];
        return;
    }
    void build()
    {
        
    }
    void update(int id,int l,int r,int index,int v)
    {
        if(l==r)
        {
            val[id]+=v;
            pos[id]=l;
            return;
        }
        
        int m=(l+r)/2;
        if(index<=m) update(lson,l,m,index,v);
        else update(rson,m+1,r,index,v);
        pushup(id);
        return;
    }
    pair<int,int> query(int id,int l,int r,int L,int R)
    {
        if((L<=l) && (r<=R))
        {
            return {pos[id],val[id]};
        }
        int ret;
        int m=(l+r)/2;
        pair<int,int> lv,rv;
        if(L<=m) lv=query(lson,l,m,L,R);
        if(R>m) rv=query(rson,m+1,r,L,R);
        ret=max(lv.second,rv.second);
        if(lv.second==ret) return lv;
        return rv;
    }
    bool cmp(pair<int,int> a,pair<int,int> b)
    {
        return a.second<b.second;
    }
    class Solution {
        
    public:
        int findMaximizedCapital(int k, int W, vector<int>& p, vector<int>& c) {
            int i,j;
            int n=p.size();
            if(!k) return W;
            for(i=0;i<n;i++) {q[i].first=p[i],q[i].second=c[i];}
            sort(q,q+n,cmp);
            for(i=0;i<n;i++) p[i]=q[i].first;
            for(i=0;i<n;i++) c[i]=q[i].second;
            memset(val,-1,sizeof(int)*(n*4+5));
            for(i=0;i<n;i++) update(1,0,n-1,i,p[i]+1);
            for(i=1;i<=k;i++)
            {
                int r=upper_bound(c.begin(),c.end(),W)-c.begin();
                r-=1;
                
                if(r<0) break;
                pair<int,int> tmp=query(1,0,n-1,0,r);
                if(tmp.second==-1) break;
                W+=tmp.second;
                update(1,0,n-1,tmp.first,-(tmp.second+1));
            }
            return W;
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.