{POJ}{3903}{Stock Exchange}{nlogn 최장 상승 서브시퀀스}

1432 단어 Exchange
제목: 최장 상승 서열 구하기, n=100000
사고방식: O(N^2) 시간 초과는 확실해...탐욕스러운 사상을 이용하여 답을 찾다.창고를 이용하여 매번 데이터를 입력하여 창고를 검사하고 2분 검색하여 그보다 가장 작은 데이터를 교체하면 창고가 더욱 좋다.이 제목은 확실히 괜찮다. 사고방식이 매우 좋다
#include <iostream>

#include <string>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <memory>

#include <cmath>

#include <bitset>

#include <queue>

#include <vector>

#include <stack>

using namespace std;

 

 

#define CLR(x,y) memset(x,y,sizeof(x))

#define MIN(m,v) (m)<(v)?(m):(v)

#define MAX(m,v) (m)>(v)?(m):(v)

#define ABS(x) ((x)>0?(x):-(x))

#define rep(i,x,y) for(i=x;i<y;++i)





const int MAXN = 110000;



int n,m;

int len;

int val;

int s[MAXN];



int BF(int cur)

{

	int low,high,mid;

	int pre;



	low = 0;

	high = len-1;

	while(low <= high)

	{

		mid = (low+high)>>1;

		if(s[mid]<cur){

			low = mid+1;

		}

		else if(s[mid]>cur){

			high = mid-1;

		}

		else 

			return mid;

	}

	return low;

}

void Solve()

{

	while(scanf("%d",&n)!=EOF)

	{

		len = 0;

		for(int i = 0 ; i < n; ++i)

		{

			scanf("%d",&val);

			if(len == 0 || s[len-1] < val){

				s[len] = val;

				++len;

			}

			else

			{

				int f = BF(val);

				s[f] = val;

			}

		}



		printf("%d
",len); } } int main() { Solve(); return 0; }

좋은 웹페이지 즐겨찾기