首页 > 编程语言 >最长上升子序列----nlogn算法-模板

最长上升子序列----nlogn算法-模板

时间:2023-09-12 12:37:08浏览次数:38  
标签:cnt include val int len ---- nlogn 模板 left



#include<iostream>
#include<vector>
#define MAX 1010
using namespace std;
vector<int> len;

// 这里我返回的满足len[k]>=val[i]且k最小的位置

// 和上文红色部分的描述是等价的,只是变成了更新len[k],而不是len[k+1]
int bisearch(int val){
    int left=0, right=len.size()-1;
    while(left<=right){
        int mid = (left+right)>>1;
        if(len[mid] < val) left = mid+1;
        else right = mid-1;
    }   
    return left;
}

int main(){
    int n, val;
    cin>>n;
    for(int i=0; i<n; ++i){
        cin>>val;
        int k = bisearch(val);
        if(len.size()==k) len.push_back(val);
        else len[k] = val;
    }   
    cout<<len.size()<<endl;
    return 0;
}


二分查找用函数:

#include<iostream>
#include<algorithm>
#define MAX 1010
using namespace std;

int p[1010];
int main(){
    int n, val;
    cin>>n;
	int cnt=0;
    for(int i=0; i<n; ++i){
        cin>>val;
        int k = lower_bound(p,p+cnt,val)-p;
        if(cnt==k) p[cnt++]=val;
        else p[k] = val;
    }   
    cout<<cnt<<endl;
    return 0;
}






标签:cnt,include,val,int,len,----,nlogn,模板,left
From: https://blog.51cto.com/u_16244339/7444303

相关文章

  • POJ 2299 Ultra-QuickSort ---归并排序 求逆序
    归并排序的模板。能求逆序。。。。#include<stdio.h>#include<string.h>intn;longlonga[500005],b[500005];longlongsum;voidmerge(intl,intm,intr){ inti=l,j=m+1,k=0; while(i<=m&&j<=r) { if(a[i]<=a[j]) b[k++]=a[i++]; else......
  • hdu 4712 Hamming Distance-----随机
    计算出二进制数中有多少个1:数据范围太大,想到可以随机如果你在第一次调用rand()之前没有调用srand(),那么系统会为你自动调用srand()。------百度rand#include<cstdio>#include<cstring>#include<algorithm>#include<time.h>usingnamespacestd;constintN=1e5+10......
  • n以内约数最多的数
    题意非常简单,问[1,n]范围内约数最多的数是几。Input输入第一行为数据组数T(T<=100)。对于每组数据,只有一个数字n(1<=n<=109 )Output对于每组数据,请在一行中输出两个数,即[1,n]范围中约数最多的那个数(如果有多个,则输出最小的那个),以及其约数的个数,用一个空格隔......
  • poj 4604 Deque-----2013多校联合赛第一场--1005
    做了一天,终于做出来了。。结题报告:考虑题目的一个简化版本:使双端队列单调上升。对于序列A和队列Q,找到队列中最早出现的数字Ax,则Ax将Q分成的两个部分分别是原序列中以Ax开始的最长上升和最长下降序列,答案即为这两者之和的最大值。而对于本题,由于存在相同元素,所以只要找到以Ax......
  • poj 4607 Park Visit --2013多校联合赛第一场---1008
    解题报告:首先如果k小于等于直径长度,那么答案为k−1。如果k大于直径长度,设直径长度为r,那么答案为r−1+(k−r)∗2。 先找树的最长路;找树中任意一点,dfs找该点所能达到的最远的点vv,然后从vv点dfs找树的最长路。。#include<stdio.h>#include<string.h>#include<vector>#includ......
  • poj 1469 COURSES----二分图
    二分图的最大匹配,模板。。#include<stdio.h>#include<string.h>booledge[110][310],visited[310];intcx[110],cy[310];intn,m;intpath(intu){ intv; for(intv=1;v<=m;v++) if(edge[u][v]&&!visited[v]){ visited[v]=1; if(cy[v]==-1||......
  • poj 1325 Machine Schedule---二分图求最小顶点覆盖
    二分图求最小顶点覆盖。。注意本题说,机器开始在0开始,所以就是默认和0相连的job已经被完成了,所以我是从1开始扫的点正常的话,要将edge【】【】和0相连的边值赋为0,表示该job已经被完成。。。#include<stdio.h>#include<string.h>booledge[110][110],visited[110];intcx[110],cy......
  • UVA-1401 - Remember the Word -----Trie前缀树
    题意:给出N个不同单词和一个长字符串S。把这个字符串分解成若干个单词的连接(单词尅重复使用),问有多少种方法?分析:令d[i]表示从字符i开始的字符串的分解方案数,则d[i]=sum{d[i+len[x]]|单词x是S[i...len]的前缀};详看《算法竞赛入门经典》---刘汝佳--Page208.......
  • 高精度加减法模板
    正整数+-法#include<stdio.h>#include<string.h>voidplus(char*a,char*b,char*c);voidminus(char*a,char*b,char*c);voidminus(char*a,char*b,char*c){ inti,j,k; intla=strlen(a); intlb=strlen(b); intflag=0; memset(c,0......
  • 进制转换
    有多组测试用例,输入一段字符s,n,k; n表示字符s是n进制的数,k表示要转换为k进制的数;例:3 10 2   715 10 16   F#include<stdio.h>#include<string.h>#include<math.h>intmain(){ chara[30],c[30]; intb[30]; intn,m,i,j,k; while(scanf("%s%d%d",a,&n......