HDU 5821 Ball (排序)

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

有n个盒子，每个盒子最多装一个球。

现在进行m次操作，每次操作可以将l到r之间盒子的球任意交换。

问进行上述操作后，是否能变成指定的状态。

将颜色相同的球，尽量靠最终状态近的分配。对于每次操作按最终序号靠近进行排序。最后检查是否一致就行了。

官方题解：
假设有4个红球，初始时从左到右标为1,2,3,4。那么肯定存在一种方案，使得最后结束时红球的顺序没有改变，也是1,2,3,4。那么就可以把同色球都写成若干个不同色球了。所以现在共有n个颜色互异的球。按照最终情况标上1,2，。。，n的序号，那么贪心的来每次操作就是把一个区间排序就行了。

 //#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = 1e3 + ;

 P ball[N];

 int a[N], b[N];

 int main()

 {

     int t, n, m;

     scanf("%d", &t);

     while(t--) {

         scanf("%d %d", &n, &m);

         for(int i = ; i <= n; ++i) {

             scanf("%d", a + i);

             ball[i].first = , ball[i].second = a[i];

         }

         for(int i = ; i <= n; ++i) {

             scanf("%d", b + i);

             for(int j = ; j <= n; ++j) {

                 if(!ball[j].first && ball[j].second == b[i]) {

                     ball[j].first = i; //最终

                     break;

                 }

             }

         }

         int l, r;

         while(m--) {

             scanf("%d %d", &l, &r);

             sort(ball + l, ball + r + );

         }

         bool ok = true;

         for(int i = ; i <= n; ++i) {

             if(ball[i].first != i) {

                 ok = false;

                 break;

             }

         }

         printf("%s\n", ok ? "Yes" : "No");

     }

     return ;

 }

巴特西

HDU 5821 Ball (排序)

最新文章

热门文章