글 읽기 - nlogn도 너무 느린건가요..

wlssud0701 7년 전 0

n번째 데이터를 입력받으면 이전까지 모아서 벡터에 저장해 놨던 데이터중에서 몇번째인지를 2진탐색으로 찾아서 그 값을 토대로 최대 등수를 구하고 2진탐색으로 찾은 그 위치에 데이터를 끼워넣기

했는데요

얼마나 더 빠르게 해야 하는 건가요...

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
vector<int> data;
int cnt=0;
int mid,maxx;
void finder(int str, int en, int  t)
{
    if(str>en) return;

    mid=(str+en)/2;
   if(mid==cnt)return;
    if(data[mid]<t)
    {
        if(mid+1>maxx)maxx=mid+1;
        finder(mid+1,en,t);
    }
    else finder(str,mid-1,t);
}
int main()
{
    int i,a,n,sum;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a);
        maxx=0;
        sum=i;
        if(i==0)
        {
            data.push_back(a);
            printf("1\n");
            cnt++;
            continue;
        }
        finder(0,data.size(),a);
        //printf("%d %d %d\n",i,a,maxx);
        sum=sum-maxx+1;
        printf("%d\n",sum);
        if(maxx+1==data.size())data.push_back(a); else
        data.insert(data.begin()+maxx,a);
       // for(i=0;i<data.size();i++) printf("%d ",data[i]);
        ///////////cout << endl;
        cnt++;
    }

    return 0;
}

sksdong1 7년 전 2

2진 탐색은 정렬된 데이터에서만 사용 가능합니당

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

nlogn도 너무 느린건가요..

wlssud0701 7년 전 0

sksdong1 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말