题目描述 题目描述： 为了迎接奥运，市体育局举行手拉手大包围活动，开始时N个人手拉手围成一个圈。后来这些人中的一些按顺序向里面出圈形成一个新圈。从而使原圈形成一个从高到低，最低与最高连接的圈。新圈重复相同的操作，直到没有人要出圈为止。问最少要形成多少个这样的圈。 输入格式 输入：第一行N个人，第二行输入N个人的身高（每个身高中用空格隔开）N<=1000 输出格式 输出：最少形成多少个这样的圈。
本题只要把环从某一个点断开然后求lis就行了；不过这里不知道当时哪位朋友说了不用二分也可以过的= =但很明显我写搓了，结果没二分80；所以研究了dalao的二分球lis的代码，发现还挺巧妙的； 不说了，代码献上；
#include <iostream> #include <string.h> #include <algorithm> #include <vector> #include <stdio.h> #include <stack> #include <queue> #include <map> using namespace std; typedef long long ll; int n; int hig[20005],h[20005]; int cnt; int getans(int fir) { memset(hig,0,sizeof(hig)); cnt=1; hig[1]=h[fir]; for(int i=fir+1;i<fir+n;i++) { if(h[i]>=hig[cnt]) hig[++cnt]=h[i]; else { int lef=1; int rig=cnt; while(rig-lef>1) { int mid=(lef+rig)>>1; if(h[i]>=hig[mid]) lef=mid; else rig=mid; } int res; if(h[i]>=hig[rig]) res=rig; else if(h[i]>=hig[lef]) res=lef; else res=0; hig[res+1]=min(hig[res+1],h[i]); } } return cnt; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&h[i]); } for(int i=n+1;i<n*2;i++) { h[i]=h[i-n]; } int ans=999999999; for(int i=1;i<=n;i++) { ans=min(ans,getans(i)); } printf("%d\n",ans); }