1672D - Cyclic Rotation
逆向思维:
b 能否转成 a ?
选择一个位置 j,
b
j
?
1
=
=
b
j
b_{j-1} == b_j
bj?1?==bj?, 那么可以把 j-1 这个位置的值放到前面去
双指针实现:
i
f
(
b
j
=
=
a
i
)
if(b_j ==a_i)
if(bj?==ai?) i ++, j ++;
i
f
(
b
j
=
=
b
j
?
1
)
if(b_j == b_{j-1})
if(bj?==bj?1?) 在mutiset中寻找是否出现过
b
j
?
1
b_{j-1}
bj?1? ,如果出现过意味着可以把它插入之前的某个位置
e
l
s
e
?
c
n
t
[
a
[
i
]
]
+
+
else \ cnt[a[i]]++
else?cnt[a[i]]++ 插入到multiset 中去,检查后边是否出现过?
while(T--)
{
int n;
cin >> n;
vector<int> a(n), b(n), cnt(n+1,0);
for(auto& x : a) cin >> x;
for(auto& x : b) cin >> x;
int i = 0, j = 0;
bool flag = true;
while(j < n) {
if(i < n && j < n && a[i] == b[j]) {i++; j++;continue;}
if(cnt[b[j]] > 0 && b[j] == b[j-1]) cnt[b[j++]]--;
else if(i < n) { cnt[a[i++]]++; }
else {flag = false; break; }
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
|