首页 > ACM题库 > HDU-杭电 > hdu 3564-another lis-线段树-[解题报告]hoj
2014
11-05

hdu 3564-another lis-线段树-[解题报告]hoj

Another LIS

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 936    Accepted Submission(s): 328

Problem Description
There is a sequence firstly empty. We begin to add number from 1 to N to the sequence, and every time we just add a single number to the sequence at a specific position. Now, we want to know length of the LIS (Longest Increasing Subsequence)
after every time’s add.
 

Input
An integer T (T <= 10), indicating there are T test cases.
For every test case, an integer N (1 <= N <= 100000) comes first, then there are N numbers, the k-th number Xk means that we add number k at position Xk (0 <= Xk <= k-1).See hint for more details.
 

Output
For the k-th test case, first output "Case #k:" in a separate line, then followed N lines indicating the answer. Output a blank line after every test case.
 

Sample Input
1 3 0 0 2
 

Sample Output
Case #1: 1 1 2
Hint
In the sample, we add three numbers to the sequence, and form three sequences. a. 1 b. 2 1 c. 2 1 3
 

Author
standy
 

Source
 

Recommend
zhouzeyong
        本题给定一个数的序列,其中a[i]表示在第a[i]个位置插入i。输入的位置是没有顺序的。因此不能用一般的方法模拟插入,时间复杂度O(n^2)。可以用线段树。设置线段树的节点信息包含一个num表示该区间[left,right]还有的空位个数。最后一个数插入的位置a[i]肯定就是正确的位置;然后倒数第二个考虑已插入的数……于是可得最终的序列。但题目的LIS是动态的,即在每次插入后计算输出。线段树很容易球的每个元素的真实位置。依题意,最终序列da[1-n]存放的是1-n的某个排序。da[i]表示元素i在第da[i]个位置。我们从i=1开始求LIS,求得的时对应下表的LIS,但与元素的LIS等价。于是我们要求的是da[]的LIS,可以用二分的方法求解,时间复杂度为O(N*log(N))。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;


//************************************************************
//算法1的时间复杂度为O(N*log(N))
const int MAXN=100000+100;
int data[MAXN];//存放原始数据
int MaxV[MAXN];//MaxV[i]存放长度为i的严格递增子序列的最大值的最小值
int ans[MAXN];
int da[MAXN];

struct node 
{
	int left,right,num;//num此处灵活处理
}tree[MAXN*4];
//1.建立以left,right为左右边界,将数组da中元素存储在首地址从1开始的线段树tree的叶节点上
void Build( int id,int left,int right)
{
    tree[id].left=left;
    tree[id].right=right;
	tree[id].num=right-left+1;//此处灵活处理
    if(left==right)
		return ;
    else
    {
		int mid =(left+right)>>1;        
        Build(id<<1,left,mid);
        Build((id<<1)|1,mid+1,right);
   }
}

void Updata(int id,int pos,int val)
{
    tree[id].num--;
    if(tree[id].left==tree[id].right)
    {
		da[val]=tree[id].left;//val表示第几次操作,da[】存储的位置
        return ;
    }
	if(tree[id<<1].num>=pos) 
        Updata(id<<1,pos,val);
    else 
		Updata((id<<1)|1,pos-tree[id<<1].num,val);
}

//二分查找返回MaxV中大于等于x的组靠左的下标
int BinaryResearch(int x,int len)
{
	int mid,low=1,high=len;
	while(low<=high)
	{
		mid=(low+high)>>1;
		if(MaxV[mid]<x)
			low=mid+1;
		else high=mid-1;
	}
	return low;
}
//返回原序列中严格递增子序列的最长长度
void LIS(int n)
{
	int i,len=0;
	for(i=1;i<=n;i++)
	{
		if(i==0||da[i]>MaxV[len])//比长度为len的子序列最大值大,直接加进末尾
			MaxV[++len]=da[i];
		else 
		{
			int pos=BinaryResearch(da[i],len);
			MaxV[pos]=da[i];
		}
		ans[i]=len;
	}
}
//===============================================

int main()
{
	int cas,i,n,tag=1;
	cin>>cas;
	while(cas--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&data[i]);
			data[i]++;
		}
		Build(1,1,n);
		for(i=n;i>=1;i--)
		{
			Updata(1,data[i],i);
		}

		LIS(n);

		printf("Case #%d:\n",tag++);

	for(i=1;i<=n;i++)
			printf("%d  ",da[i]);
		printf("*******\n");

		
		for(i=1;i<=n;i++)
			printf("%d\n",ans[i]);
		printf("\n");
	}
	system("pause");
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  5. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  6. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。