2016-08-15

HDU 5821 Ball【脑洞】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5821

题意：

给定初始序列和目标序列，给定若干区间，按给定的顺序，可以依次改变区间中数的排列，问能否达到目标序列。

分析：

这题好难。
首先明确：颜色相同的球中，每个球对应的目标位置的相对顺序与该球原来的相对顺序是相同的。
那么对于初始序列中的每个元素，记录下他的目标位置，为使他越来越靠近他的目标位置，在操作区间内按目标位置不停排序，排到前面就意味着他被换到前面的位置，反之相同。这样他就不停的靠近目标位置，最后看这个目标位置是否到达即可。
最初写的版本对于每个元素，遍历每个区间，记录下目标与边界的差值，然后不停的移动乱搞。。其实直接排个序就可以巧妙解决。。
智商啊我要智商。

代码：

/*************************************************************************
    > File Name: 8.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/11 10:20:15
 ************************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
typedef pair<int, int>p;
const int maxn = 1e3 + 5;
int a[maxn], b[maxn];
int ans[maxn];
struct OP{
    int l, r;
}op[maxn];
int main (void)
{
    int T;scanf("%d", &T);
    while(T--){
	    queue<int>q[maxn];
        int n, m;scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
		}
        for(int i = 0; i < n; i++){
            scanf("%d", &b[i]);
			q[b[i]].push(i);
        }
        bool flag = true;
		for(int i = 0; i < n; i++){
			if(q[a[i]].empty()){
				flag = false;
				break;
			}
			ans[i] = q[a[i]].front();
			q[a[i]].pop();
		}
        for(int i = 0; i < m; i++){
            scanf("%d%d", &op[i].l, &op[i].r);
        }
		if(!flag){
			puts("No");
            continue;
        }
        for(int i = 0; i < m; i++){
			sort(ans + op[i].l - 1, ans + op[i].r);
        }
        for(int i = 0; i < n; i++){
            if(ans[i] != i){
                flag = false;
                break;
            }
        }
        if(!flag) puts("No");
        else puts("Yes");
    }
    return 0;
}