CodeForces - 356A Knight Tournament

http://codeforces.com/problemset/problem/356/A

首先理解题意

每次给出l 和r 在l　－　ｒ之间还有资格的选手中得出一个胜者

暴力思路:

首先维护还有资格的选手的集合

用一个数组表示这个选手被谁击败

每次遍历 l - r 然后把不是胜者且还在集合中的选手踢出并更新这个选手的数组值

最终输出这个数组即可

这样会TLE

1、如果用数组维护这个集合的话每次遍历都是这样就是O(n^2) -->> 所以用set维护这个集合

2、使用set后如果每次依然从l - r去遍历找在集合中的元素去find的话那么就会在 (l, r)的区间两端有浪费的运算如果每次l, r 都是1 和 n的话那就浪费得非常得多

　　所以使用set :: lower_bound() 直接得到第一个大于l 并在集合中的元素 O(logn)

这样优化后即可

 #include <iostream>

 #include <stdio.h>

 #include <set>

 using namespace std;

 int Par[];

 int tmp[];

 set<int> s;

 int find(int x)

 {

     if (Par[x] == x) return x;

     else return find(Par[x]);

 }

 int main()

 {

     int n, m;

     freopen("in.txt", "r", stdin);

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

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

     {

         Par[i] = i;

         s.insert(i);//加入set中

     }

     for(int i = ; i < m; i++)

     {

         int l, r, x;

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

         set<int> :: iterator pit = s.lower_bound(l);//返回第一个>= l的位置

         int num = ;

         while (pit != s.end() && (*pit) <= r )

         {

             if ((*pit) != x)

             {

                 Par[*pit] = x;

                 //s.erase(*pit); 不能在这里直接删除 删除后set结构发生改变 pit就失效了

                 tmp[num++] = *pit;

             }

             pit++;

         }

         for (int j = ; j < num; j++) s.erase(tmp[j]);

     }

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

     {

         if (Par[i] == i) printf("0 ");

         else printf("%d ", Par[i]);

     }

     putchar('\n');

 }

巴特西

CodeForces - 356A Knight Tournament

最新文章

热门文章