题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1319
题目大意：就是求最长递增子序列，并输出位置。。。。
思路：先把s进行升序排列，然后把b按降序排列，最后把找出b的最长递增子序列。。。。
先给两个最长递增子序列的模板：了解更多轻点这儿。。。。。。
时间复杂度：O（log（n*n））
unsigned int LISS(const int array[], size_t length, int result[])
{
unsigned int i, j, k, max;
//变长数组参数，C99新特性，用于记录当前各元素作为最大元素的最长递增序列长度
unsigned int liss[length];
//前驱元素数组，记录当前以该元素作为最大元素的递增序列中该元素的前驱节点，用于打印序列用
unsigned int pre[length];
for(i = 0; i < length; ++i)
{
liss[i] = 1;
pre[i] = i;
}
for(i = 1, max = 1, k = 0; i < length; ++i)
{
//找到以array[i]为最末元素的最长递增子序列
for(j = 0; j < i; ++j)
{
//如果要求非递减子序列只需将array[j] < array[i]改成<=，
//如果要求递减子序列只需改为>
if(array[j] < array[i] && liss[j] + 1> liss[i])
{
liss[i] = liss[j] + 1;
pre[i] = j;
//得到当前最长递增子序列的长度，以及该子序列的最末元素的位置
if(max < liss[i])
{
max = liss[i];
k = i;
}
}
}
}
//输出序列
i = max - 1;
while(pre[k] != k)
{
result[i--] = array[k];
k = pre[k];
}
result[i] = array[k];
return max;
}
时间复杂度：O（nlog（n））
unsigned int LISSEx(const int array[], size_t length, int result[])
{
unsigned int i, j, k, l, max;
//栈数组参数，C99新特性，这里的liss数组与上一个函数意义不同，liss[i]记录长度为i + 1
//递增子序列中最大值最小的子序列的最后一个元素（最大元素）在array中的位置
unsigned int liss[length];
//前驱元素数组，用于打印序列
unsigned int pre[length];
liss[0] = 0;
for(i = 0; i < length; ++i)
{
pre[i] = i;
}
for(i = 1, max = 1; i < length; ++i)
{
//找到这样的j使得在满足array[liss[j]] > array[i]条件的所有j中，j最小
j = 0, k = max - 1;
while(k - j > 1)
{
l = (j + k) / 2;
if(array[liss[l]] < array[i])
{
j = l;
}
else
{
k = l;
}
}
if(array[liss[j]] < array[i])
{
j = k;
}
//array[liss[0]]的值也比array[i]大的情况
if(j == 0)
{
//此处必须加等号，防止array中存在多个相等的最小值时，将最小值填充到liss[1]位置
if(array[liss[0]] >= array[i])
{
liss[0] = i;
continue;
}
}
//array[liss[max -1]]的值比array[i]小的情况
if(j == max - 1)
{
if(array[liss[j]] < array[i])
{
pre[i] = liss[j];
liss[max++] = i;
continue;
}
}
pre[i] = liss[j - 1];
liss[j] = i;
}
//输出递增子序列
i = max - 1;
k = liss[max - 1];
while(pre[k] != k)
{
result[i--] = array[k];
k = pre[k];
}
result[i] = array[k];
return max;
}
AC code：
#include
#include
#include
#include
using namespace std; struct Node { int s,b,id; //记录s，b，还有开始的位置 }node[100010]; bool cmp(Node t1,Node t2) { return t1.s
t2.b); } unsigned int LISSEx(const Node array[], size_t length, int result[]) { unsigned int i, j, k, l, max; //栈数组参数，C99新特性，这里的liss数组与上一个函数意义不同，liss[i]记录长度为i + 1 //递增子序列中最大值最小的子序列的最后一个元素（最大元素）在array中的位置 unsigned int liss[length]; //前驱元素数组，用于打印序列 unsigned int pre[length]; liss[0] = 0; for(i = 0; i < length; ++i) { pre[i] = i; } for(i = 1, max = 1; i < length; ++i) { //找到这样的j使得在满足array[liss[j]] > array[i]条件的所有j中，j最小 j = 0, k = max - 1; while(k - j > 1) { l = (j + k) / 2; if(array[liss[l]].b < array[i].b) { j = l; } else { k = l; } } if(array[liss[j]].b < array[i].b) { j = k; } //array[liss[0]]的值也比array[i]大的情况 if(j == 0) { //此处必须加等号，防止array中存在多个相等的最小值时，将最小值填充到liss[1]位置 if(array[liss[0]].b >= array[i].b) { liss[0] = i; continue; } } //array[liss[max -1]]的值比array[i]小的情况 if(j == max - 1) { if(array[liss[j]].b < array[i].b) { pre[i] = liss[j]; liss[max++] = i; continue; } } pre[i] = liss[j - 1]; liss[j] = i; } //输出递增子序列 i = max - 1; k = liss[max - 1]; while(pre[k] != k) //记录排序后得到的最长递增子序列的位置 { result[i--] = k; k = pre[k]; } result[i] = k; return max; } int result[100010],array[100010]; int main() { int n,i; int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0;i