如题~
感觉我的思路很复杂的样子,首先要用结构体记录下标编号,通过排序进行去重~再用排序后用二分法找到要链接的下标求连通分量,最后后根据连通分量求最长路径~

虽然我知道我在讲天书,但感觉这题应该存在简单高效的算法吧希望各位大神能给出可行的参考算法~

[此贴子已经被作者于2018-3-18 15:24编辑过]

问题是难度居然是基础题,我也是醉了,或者普通算法也能达到目的,有大神能给出一个可行能够AC的算法就可以了~

好我去看看情况,有消息和你说说,希望简单改下条件可以AC~

ACM题目通过了叫AC
当然我是帮我的一个同学问的,我还要等他消息,有点无语~

2楼代码输入
10
100 150 200 300
201 202 203 204
9 8

的时候输出结果为5
期望结果应该是7
PS:8楼也是~
2018-3-18 22:25更~

[此贴子已经被作者于2018-3-18 22:27编辑过]

学习了

这个方法的确挺巧妙的~应该可以了~

然后发现了原来是用了路径覆盖思想,的确比我那个求连通分量要简单很多,当然我那个方法理论上可以输出最长路径的~
当然了,能AC就可以了~

[此贴子已经被作者于2018-3-19 08:04编辑过]

这个是常规算法,容易理解~
就是用常规算法进行查找来获取位置 ~
但如果要卡效率的话这算法复杂度o(n^2)有可能超时哦~

重写了sbeach函数,实现形式参考了标准库函数bsearch,实现主体参考了12楼的代码(特别拜谢),当然个人感觉14楼的二分法查找下标从1开始适用范围比较有局限性
这个函数感觉这个对于查找最近插入点有一定帮助的,可以参考一下~

size_t BsearchReIndex( const void* key,const void* base,size_t num,size_t size,int (*compartor)( const void*,const void* ) )
{
   size_t low=0;
   size_t height=num-1;
   
   while (low<=height&&height!=-1)
   {
       const size_t mid=low+(height-low>>1);
       
     const int comp=compartor(key,( const char* )base+mid*size);
       
    if (comp<0)
        height=mid-1;
    else if (comp>0)
        low=mid+1;
    else
        return mid;
   }

   return low;
}

写了个输出路径的,感觉有点绕,看看就行了~

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

#define FREE( p )    \
    do    \
    {    \
        free(p);    \
        p=NULL;    \
    }while (0)

typedef struct Data
{
    int data;    //保存数据
    size_t mark;    //上一个数据下标
    
}Data,*P_Data;

size_t _bsearch( const void*,const void*,size_t,size_t ,int (*)( const void*,const void* ));

int comp(const void* ,const void* );

void malFun( void**,size_t );
void input( const P_Data*,size_t );

void printData( const Data[],size_t );

unsigned fun( Data[],size_t );

int main( void )
{
    P_Data data=NULL;
    
    size_t len=0;
    
    if ( !scanf("%u",( unsigned* )&len))
        exit(EXIT_FAILURE);

    input(&data,len);

    printData(data,fun(data,len));
    
    FREE(data);

    return 0;
}

int comp(const void* p,const void* q)
{
    const int _p=*( const int* )p;
    const P_Data _q=( const P_Data )q;

    if (_p>_q->data)
        return 1;
    
    if (_p<_q->data)
        return -1;
        
    return 0;
}

size_t _bsearch( const void* key,const void* base,size_t num,size_t size,int (*compartor)( const void*,const void* ) )
{
   size_t low=0;
   size_t height=num-1;
   
   while (low<=height&&height!=-1)
   {
       const size_t mid=low+(height-low>>1);
       
     const int comp=compartor(key,( const char* )base+mid*size);

    if (comp<0)
        height=mid-1;
    else if (comp>0)
        low=mid+1;
    else
        return mid;
   }

   return low;
}

void malFun( void** data,size_t size )
{
    assert(data);
    
    *data=malloc(size);
    
    assert(*data);
    
    memset(*data,0,size);
}

void input( const P_Data* data,size_t len)
{
    const size_t size=len*sizeof (Data);
    size_t i;
    
    if (!len)
        exit(EXIT_FAILURE);
    
    malFun(( void** )data,size);
    
    for (i=0;i!=len;++i)
        if (!scanf("%d",&(*data)[i].data))
            exit(EXIT_FAILURE);
        else
            (*data)[i].mark=i;
            
       
}

unsigned fun( Data data[],size_t len )
{
    P_Data road=NULL;

    const size_t dataSize=len*sizeof (Data);
    const size_t roadSize=len*sizeof (Data);
    
    size_t pos=0;
    
    size_t i;
    size_t j=1;
    
    malFun(( void** )&road,roadSize);
    
    road[0].data=data[0].data;
    road[0].mark=0;

    for (i=0;i!=len;++i)
        data[i].mark=-1;
    
    for (i=1;i<len;++i)
    {
        if (data[i].data>road[j-1].data)
            pos=j++;
        else
            pos=_bsearch(&data[i].data,road,j,sizeof (Data),comp);

       if (pos)
            data[i].mark=road[pos-1].mark;
        
        road[pos].data=data[i].data;
        road[pos].mark=i;

    }
    
    pos=road[j-1].mark;
   
   FREE(road);

    return pos;
}

void printData( const Data data[],size_t mark )
{
    int* road=NULL;
    
    size_t step;
    size_t t_step;
    
    size_t t_mark=mark;
    
    for (step=0;mark!=-1;++step)
        mark=data[mark].mark;

    malFun(( void** )&road,step*sizeof (int));
    
    for (t_step=step-1,mark=t_mark;mark!=-1;--t_step)
    {
        road[t_step]=data[mark].data;
        mark=data[mark].mark;
    }

     printf("\n最长子序列长度为%u,具体路径为:\n",( unsigned )step);
    while (++t_step!=step)
        printf("%-8d",road[t_step]);
    
    puts("");
    FREE(road);
}

[此贴子已经被作者于2018-3-20 08:28编辑过]

赶紧吃个瓜来缓冲一下~