0

SPOJ からの問題文は次のとおりです。通常の DP ソリューションから始めましたが、n^2 の時間がかかり、制限時間を超えることは避けられませんでした。

問題に対する nlogn ソリューションに出会いました。これがそのソリューションです。

最長増加サブシーケンスの長さを見つける必要がある場合、またはシーケンスの 1 つも見つけなければならない場合、このソリューションはうまく機能します。しかし、あるシーケンスまたは他のシーケンスの一部であるすべての要素を見つける必要がある場合は、いくつかのストレージやその他のことを行い、このソリューションに到達しました.

現在、これは SPOJ エンジンによって予期されていましたが、受け入れられている他のソリューションを見ると、私のプログラムは 0.48 時間かかり、他のプログラムは 0.04 時間しかかかりません。

可能であれば、ソリューションを改善する方法を教えてもらえますか?

私がソリューションで行っていることは、出力配列に現在の数値だけでなくリスト全体を格納していることです。親では、各数値が出力の一部になるため、すべての親を維持しています。配列。

最終的な配列は、その数値が LIS に属するかどうかのブール値を格納する最終的な整数配列にすぎません。

ありがとう

PS ideone.com へのリンクにはコードを添付する必要があると記載されているため、ここにコード自体を貼り付けます。

#include<stdio.h>
#include<stdlib.h>

int count;

struct node{
    int value;
    struct node* next;
};

int constructFinal(int *final,struct node **parent,struct node **output,int value){
    if(final[value - 1] == 1)
        return 0;
    final[value - 1] = 1;
    count++;
    struct node* temp;
    temp = parent[value-1];
    while(temp!= NULL){
        constructFinal(final,parent,output,temp->value);
        temp = temp->next;
    }
}

int findIndex(int currentElement,struct node** output,int lower,int upper){
    if(lower >= upper)
        return lower;
    int mid =lower + ( upper - lower )/2;
    if(output[mid]->value < currentElement)
        return findIndex(currentElement,output,mid+1,upper);
    else if(output[mid]->value > currentElement)
        return findIndex(currentElement,output,lower,mid);
}   

int main(){
    int numOfInp,sizeOfInp,i,currentElement,sizeOfOut,indexBinary,indexAdded;
    struct node *temp,*tempIter;
    numOfInp=1;
    while(numOfInp--){
        scanf("%d",&sizeOfInp);
        struct node **output; // if I initialise normal initialisation, I may not get the data as 0 by default, hence callocing
        struct node **parent;
        int *input;
        input = (int *)calloc(sizeOfInp,sizeof(int));
        for(i=0 ; i< sizeOfInp ; i++)
            scanf("%d",&input[i]);

        parent = (struct node**)calloc(sizeOfInp, sizeof(struct node*));

        output = (struct node**)calloc(sizeOfInp, sizeof(struct node*));
        sizeOfOut = 0;
        for(i=0;i<sizeOfInp;i++){
            indexBinary = -1;
            currentElement = input[i];
            if(sizeOfOut == 0){
                output[sizeOfOut] = (struct node*)calloc(1,sizeof(struct node));
                output[sizeOfOut]->value = currentElement;
                indexAdded = sizeOfOut;
                sizeOfOut++;
            }
            else{
                if(currentElement > output[sizeOfOut-1]->value){
                    output[sizeOfOut] = (struct node*)calloc(1,sizeof(struct node));
                    output[sizeOfOut]->value = currentElement;
                    indexAdded = sizeOfOut;
                    sizeOfOut++;
                }
                else{
                    indexBinary = findIndex(currentElement,output,0,sizeOfOut-1);
                    temp = (struct node*)calloc(1,sizeof(struct node));
                    temp->next = output[indexBinary];
                    output[indexBinary] = temp;
                    output[indexBinary]->value = currentElement;
                    indexAdded = indexBinary;
                }
            }

            //parent[currentElement-1] = (struct node*)calloc(sizeof(struct node));
            if(indexAdded > 0){
                tempIter = output[indexAdded-1];
                while(tempIter != 0 && tempIter->value < currentElement){               //for all the elements in the previous bucket
                    temp = (struct node*)calloc(1,sizeof(struct node)); //add the values to parent
                    temp->next = parent[currentElement-1];
                    parent[currentElement-1] = temp;
                    parent[currentElement-1]->value = tempIter ->value;
                    tempIter = tempIter->next;
                }
            }
            else{
                parent[currentElement-1] = NULL;    // these are the elements in the first bucket of output
            }
        }

        int *final;
        final = (int*)calloc(sizeOfInp,sizeof(int));
        temp = output[sizeOfOut -1];
        count=0;
        while(temp != NULL){
            constructFinal(final,parent,output,temp->value);
            temp=temp->next;
        }
        printf("%d\n",count);
        for(i=0;i<sizeOfInp;i++)
            if(final[i]==1)
                printf("%d ",i+1);
        printf("\n");
        free(output);
        free(parent);

    }
    return 0;
}
4

1 に答える 1

1

1 つの提案 (これはおそらくほんの少ししか役に立ちません) は、calloc を何度も呼び出さないようにすることです。

これを行うには、最大サイズの単一の配列を事前に割り当て、その中に割り当てられた要素の数を追跡します。

関数呼び出しのオーバーヘッドを回避できるため、再帰関数呼び出しを単一の反復関数に変更することも役立つ場合があります。

于 2014-01-20T10:25:38.697 に答える