一个奇葩的问题
查看原帖
一个奇葩的问题
270791
WanderingTrader楼主2020/5/4 16:48

RT

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int pos1[N],pos2[N],seq[N],n;
int find_(const int goal,const int left,const int right){
	int l = left,r = right,mid,ans ;
	if(l == r)return l - 1;
	while(l < r){
		mid = (l + r) / 2;
		if(seq[mid] > goal)
			r = mid;
		else { l = mid + 1 ; ans = mid;}
	}
	return ans;
}
int solve()				//二分求LCS 
{
	int l = 1;
	seq[1] = pos2[1];
	for(int i = 2;i <= n;i ++)
	{
		if(pos2[i] >= seq[l])
			seq[++ l] = pos2[i];
		else 
			seq[find_(pos2[i],1,l) + 1] = pos2[i];	//插入 
//		for(int j = 1;j <= l;j ++)
//			cout << seq[j] << " ";
		printf("\t%d\n",l);
	}
	return l;
}
int main(){
	scanf("%d",&n);
	for(int i = 1,u;i <= n;i ++)
	{
		scanf("%d",&u);	
		pos1[u] = i;	
	}
	for(int i = 1,u;i <= n;i ++)
	{
		scanf("%d",&u);
		pos2[i] = pos1[u];
	}
	cout << solve() << endl;
	for(int i = 1;i <= n;i ++)
		cout << pos2[i] << " ";
	return 0;
}

中间代码块里的两行注释是有什么特异功能吗

| 50 |

| 12 1 3 22 39 13 35 25 21 50 33 27 42 36 6 11 46 20 48 8 4 5 30 29 17 15 34 45 38 16 41 32 47 9 44 26 37 19 2 7 49 31 40 14 10 43 24 23 18 28 |

| 9 16 8 38 7 22 13 6 24 28 29 1 44 48 25 26 50 46 40 10 14 23 37 43 47 42 3 30 35 15 2 11 41 45 18 20 19 32 21 4 34 39 31 36 33 12 27 49 5 17 |

这组数据,答案是10,中间两行注释打开就输出10,没打开就输出11,什么操作……

大佬可以解答一下吗,谢谢

2020/5/4 16:48
加载中...