http://acm.hdu.edu.cn/showproblem.php?pid=5821
HDU 5821 – Ball [思路/贪心] | codekun
给定两个长度为N的数列A和B,有M次操作,每次可以把Li到Ri段的数字打乱重排,问你能否通过M次操作把A变成B
Read full article from HDU 5821 – Ball [思路/贪心] | codekun
ZZX has a sequence of boxes numbered 1,2,...,n . Each box can contain at most one ball.
You are given the initial configuration of the balls. For1≤i≤n , if the i -th box is empty then a[i]=0 , otherwise the i-th box contains exactly one ball, the color of which is a[i], a positive integer. Balls with the same color cannot be distinguished.
He will perform m operations in order. At the i-th operation, he collects all the balls from boxes l[i],l[i]+1,...,r[i]-1,r[i], and then arbitrarily put them back to these boxes. (Note that each box should always contain at most one ball)
He wants to change the configuration of the balls from a[1..n] to b[1..n] (given in the same format as a[1..n]), using these operations. Please tell him whether it is possible to achieve his goal.
You are given the initial configuration of the balls. For
He will perform m operations in order. At the i-th operation, he collects all the balls from boxes l[i],l[i]+1,...,r[i]-1,r[i], and then arbitrarily put them back to these boxes. (Note that each box should always contain at most one ball)
He wants to change the configuration of the balls from a[1..n] to b[1..n] (given in the same format as a[1..n]), using these operations. Please tell him whether it is possible to achieve his goal.
Input
First line contains an integer t. Then t testcases follow.
In each testcase: First line contains two integers n and m. Second line contains a[1],a[2],...,a[n]. Third line contains b[1],b[2],...,b[n]. Each of the next m lines contains two integers l[i],r[i].
1<=n<=1000,0<=m<=1000, sum of n over all testcases <=2000, sum of m over all testcases <=2000.
0<=a[i],b[i]<=n.
1<=l[i]<=r[i]<=n.
In each testcase: First line contains two integers n and m. Second line contains a[1],a[2],...,a[n]. Third line contains b[1],b[2],...,b[n]. Each of the next m lines contains two integers l[i],r[i].
1<=n<=1000,0<=m<=1000, sum of n over all testcases <=2000, sum of m over all testcases <=2000.
0<=a[i],b[i]<=n.
1<=l[i]<=r[i]<=n.
Output
For each testcase, print "Yes" or "No" in a line.
Sample Input
5 4 1 0 0 1 1 0 1 1 1 1 4 4 1 0 0 1 1 0 0 2 2 1 4 4 2 1 0 0 0 0 0 0 1 1 3 3 4 4 2 1 0 0 0 0 0 0 1 3 4 1 3 5 2 1 1 2 2 0 2 2 1 1 0 1 3 2 4
Sample Output
No No Yes No Yes
给定两个长度为N的数列A和B,有M次操作,每次可以把Li到Ri段的数字打乱重排,问你能否通过M次操作把A变成B
Analysis
首先能够想到的是如果数列B中有3个2,如果能把A变成B,那么可以定为3个2之间是不交叉交换的。那么这样根据最终的序列就有一个优先级,最后越靠左的数在重排时越靠左,这样我们根据优先级对A序列编号后排序M次,看最终能否变成B即可。
正解应该是贪心,对于最左边的值,那么他一定对应着在B[i]数组中与他相同的,且最左边的数。
根据这个,贪心的去扫一遍就好了,其实就是不断排序,为什么?
因为排序之后,一定会使得从目标到结束状态花费变得最小。
typedef
pair<
int
,
int
> P;
const
int
maxn = 1024;
P A[maxn];
P seg[maxn];
int
N, M, B[maxn];
int
cnt[maxn];
bool
solve() {
for
(
int
i = 0; i <= N; ++i)
if
(cnt[i] != 0)
return
false
;
for
(
int
i = 1; i <= N; ++i) {
for
(
int
j = 1; j <= N; ++j) {
if
(A[j].first != -1)
continue
;
if
(A[j].second == B[i]) {
A[j].first = i;
break
;
}
}
}
for
(
int
i = 1; i <= M; ++i)
sort(A + seg[i].first, A + seg[i].second + 1);
for
(
int
i = 1; i <= N; ++i)
if
(A[i].second != B[i])
return
false
;
return
true
;
}
int
main() {
int
T;
scanf
(
"%d"
, &T);
while
(T--) {
scanf
(
"%d%d"
, &N, &M);
memset
(cnt, 0,
sizeof
(cnt));
memset
(A, -1,
sizeof
(A));
for
(
int
i = 1; i <= N; ++i) {
scanf
(
"%d"
, &A[i].second);
++cnt[A[i].second];
}
for
(
int
i = 1; i <= N; ++i) {
scanf
(
"%d"
, B + i);
--cnt[B[i]];
}
for
(
int
i = 1; i <= M; ++i) {
scanf
(
"%d%d"
, &seg[i].first, &seg[i].second);
}
puts
(solve() ?
"Yes"
:
"No"
);
}
return
0;
}