p*****2
发帖数: 21240 | 1 两个整数1－n的permutation, S和T
每次可以进行一种操作，把S最后一个数字拿出来放在S的任意一个位置。
问通过这种操作把S转变为T的最少操作数。
例如
3 2 1
1 2 3
ans:2
1 2 3 4 5
1 5 2 3 4
ans:1
1 5 2 3 4
1 2 3 4 5
ans:3
1<=n<=2*10^5, n很大，所以基本需要O(n)的复杂度 |
w****x
发帖数: 2483 | |
j*****n
发帖数: 1545 | |
C***U
发帖数: 2406 | 4 为什么第一个例子答案是2
两个整数1－n的permutation, S和T每次可以进行一种操作，把S最后一个数字拿出来放
在S的任意一个位置。问通过这种操作把S转变为T的最少操作数。例如3 2 11 2 ......
..
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
【在 p*****2 的大作中提到】
: 两个整数1－n的permutation, S和T
: 每次可以进行一种操作，把S最后一个数字拿出来放在S的任意一个位置。
: 问通过这种操作把S转变为T的最少操作数。
: 例如
: 3 2 1
: 1 2 3
: ans:2
: 1 2 3 4 5
: 1 5 2 3 4
: ans:1
|
w****x
发帖数: 2483 | |
j********e
发帖数: 1192 | 6 不对吧，这样第3个例子的答案就是2，而不是3了。
最长公共子序列是234
【在 w****x 的大作中提到】
: n -最长公共子序列
|
w****x
发帖数: 2483 | 7
哦,只能是最后一个
【在 j********e 的大作中提到】
: 不对吧，这样第3个例子的答案就是2，而不是3了。
: 最长公共子序列是234
|
j********e
发帖数: 1192 | 8 这个算法呢？
从左往右扫描S，对S的第一个数a，从T开始扫，直到T里面碰到a，记下T
里的位置Pa，那么至少需要(Pa-1）次操作。然后取S里的第二个数b,从
T的Pa+1位置继续找b，找到位置Pb后，(Pb-2)是至少的操作数。如此继续，
直到T为空。
int scan(int S[], int T[], int N) {
int p = 0;
int max = 0;
if(!S || !T) return 0;
for(int i=0; i
while(p < N && T[p] != S[i])
p++;
if(p == N) {
break;
}
max = p - i;
p++;
}
return max;
}
【在 p*****2 的大作中提到】
: 两个整数1－n的permutation, S和T
: 每次可以进行一种操作，把S最后一个数字拿出来放在S的任意一个位置。
: 问通过这种操作把S转变为T的最少操作数。
: 例如
: 3 2 1
: 1 2 3
: ans:2
: 1 2 3 4 5
: 1 5 2 3 4
: ans:1
|
h**6
发帖数: 4160 | 9 第一个数列左起最多连续前x项是第二个数列的子序列，这x项可以保留，因此需要移动
n-x次。 |
p*****2
发帖数: 21240 | 10
复杂度什么样子的？
【在 h**6 的大作中提到】
: 第一个数列左起最多连续前x项是第二个数列的子序列，这x项可以保留，因此需要移动
: n-x次。
|
|
|
p*****2
发帖数: 21240 | 11
复杂度如何呢？
【在 j********e 的大作中提到】
: 这个算法呢？
: 从左往右扫描S，对S的第一个数a，从T开始扫，直到T里面碰到a，记下T
: 里的位置Pa，那么至少需要(Pa-1）次操作。然后取S里的第二个数b,从
: T的Pa+1位置继续找b，找到位置Pb后，(Pb-2)是至少的操作数。如此继续，
: 直到T为空。
: int scan(int S[], int T[], int N) {
: int p = 0;
: int max = 0;
: if(!S || !T) return 0;
: for(int i=0; i
|
p*****2
发帖数: 21240 | 12
..
3 2 1
变为 1 3 2
变为 1 2 3
所以是两次
【在 C***U 的大作中提到】
: 为什么第一个例子答案是2
:
: 两个整数1－n的permutation, S和T每次可以进行一种操作，把S最后一个数字拿出来放
: 在S的任意一个位置。问通过这种操作把S转变为T的最少操作数。例如3 2 11 2 ......
: ..
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
|
j********e
发帖数: 1192 | 13 O(N)吧，han6和我的好像是相同的算法
【在 p*****2 的大作中提到】
:
: ..
: 3 2 1
: 变为 1 3 2
: 变为 1 2 3
: 所以是两次
|
p*****2
发帖数: 21240 | 14
好像O(n), 我做一下。
【在 p*****2 的大作中提到】
:
: ..
: 3 2 1
: 变为 1 3 2
: 变为 1 2 3
: 所以是两次
|
p*****2
发帖数: 21240 | 15 膜拜两位大牛。是对的。
n=int(raw_input())
l1=map(int,raw_input().split())
l2=map(int,raw_input().split())
i=0
j=0
while j
if l1[i]==l2[j]:
i+=1
j+=1
else:
j+=1
print n-i |
w****x
发帖数: 2483 | 16
这个怎么证明啊
【在 h**6 的大作中提到】
: 第一个数列左起最多连续前x项是第二个数列的子序列，这x项可以保留，因此需要移动
: n-x次。
|
d**e
发帖数: 6098 | 17 周瑜同学仍然是那么令人佩服犹如滔滔江水连绵不绝，又如黄河泛滥一发而不可收拾
【在 h**6 的大作中提到】
: 第一个数列左起最多连续前x项是第二个数列的子序列，这x项可以保留，因此需要移动
: n-x次。
|
