问题描述
有一天，一个名叫顺旺基的程序员从石头里诞生了。又有一天，他学会了冒泡排序和独立集。在一个图里，独立集就是一个点集，满足任意两个点之间没有边。于是他就想把这两个东西结合在一起。众所周知，独立集是需要一个图的。那么顺旺基同学创造了一个算法，从冒泡排序中产生一个无向图。
这个算法不标准的伪代码如下：
procedure bubblesortgraph(n, a[]) ：
/*输入：点数n，1到n的全排列a。
输出：一个点数为n的无向图G。*/
创建一个有n个点，0条边的无向图G。
repeat
swapped = false
for i 从 1 到 n-1 ：
if a[i] > a[i + 1] ：
在G中连接点a[i]和点a[i + 1]
交换a[i]和a[i + 1]
swapped = true
until not swapped
输出图G。
//结束。
那么我们要算出这个无向图G最大独立集的大小。但是事情不止于此。顺旺基同学有时候心情会不爽，这个时候他就会要求你再回答多一个问题：最大独立集可能不是唯一的，但有些点是一定要选的，问哪些点一定会在最大独立集里。今天恰好他不爽，被他问到的同学就求助于你了。
输入
两行。第一行为N，第二行为1到N的一个全排列。
输出
两行。第一行输出最大独立集的大小，第二行从小到大输出一定在最大独立集的点的编号(输入时的序号)。
输入输出样例
bubble.in
3
3 1 2
bubble.out
2
2 3
30%的数据满足 N<=16数据范围
60%的数据满足 N<=1,000
100%的数据满足 N<=100,000
这道题的第一问其实就是最长上升子序列，第二问求必是最长上升子序列里的元素有哪些，我们就只需要正着跑一遍再反着跑一遍就行了。
上代码
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int s=0,m=1;char ch=getchar();
while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘))ch=getchar();
if(ch==‘-‘)m=-1,ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
return s*m;
}
int B[100005],sec;
int a[100005],b[100005];
int A[100005],fir;
int L[100005],R[100005];
int n;
map<pair<int, int>, int> Pair;
int main(){
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
b[i]=-a[i];
}
for(int i=1;i<=n;i++)
{
int pos=lower_bound(A+1,A+1+fir,a[i])-A;
L[i]=pos;
fir+=int(A[pos]==0);
A[pos]=a[i];
}
for(int i=1;i<=n;i++) B[i]=-1e9+7;
for(int i=n;i>=1;i--)
{
int pos=lower_bound(B+1,B+1+sec,b[i])-B;
R[i]=pos;
sec+=int(B[pos]==-1e9+7);
B[pos]=b[i];
}
cout<<fir<<endl;
for(int i=1;i<=n;i++)
if(L[i]+R[i]-1==fir)
Pair[make_pair(L[i],R[i])]++;
sec=0;
for(int i=1;i<=n;i++)
if(L[i]+R[i]-1==fir&&Pair[make_pair(L[i],R[i])]==1)
B[++sec]=i;
for(int i=1;i<=sec;i++)
cout<<B[i]<<" ";
return 0;
}
原文：https://www.cnblogs.com/Yoicanblog/p/13546880.html