HDU 5821 Ball （排序、思维题）

本文主要是介绍HDU 5821 Ball （排序、思维题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5821

题意：有t组数据，每组数据第一行n表示n个盒子，m个操作，下两行两个序列a和b，表示每个盒子有一种颜色的球，颜色相同的无法分辨。给出m个操作，每个操作l和r表示可以将序列a中从编号l到r的盒子中的球任意排序。问你m个操作后能否将序列a变为序列b。

官方题解说得不明不白...意思就是同种颜色的球在m个操作后相对位置是不变的，仔细想想确实是这样。所以我们就可以给每个球编号，然后对a中l到r的数按照其在b中的下标排序，由于前面说的理论，相同颜色的球就从左向右编号就好啦。m次排序之后看看得到的新序列是否和b相同就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
P s[1010];
int d[1010];
int main() {int t;scanf("%d", &t);while(t--) {int n, m;scanf("%d %d", &n, &m);int i, j;for(i = 0; i < n; i++) {scanf("%d", &s[i].second);s[i].first = -1;}for(i = 0; i < n; i++) {scanf("%d", d + i);for(j = 0; j < n; j++) {if(s[j].second == d[i] && s[j].first == -1) {s[j].first = i;break;}}}int l, r;for(i = 0; i < m; i++) {scanf("%d %d", &l, &r);sort(s + l - 1, s + r);}int flag = 0;for(i = 0; i < n; i++) {if(s[i].second != d[i]) {flag = 1;break;}}if(flag) puts("No");else puts("Yes");}return 0;
}

这篇关于HDU 5821 Ball （排序、思维题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---