codeforces 555B Case of Fugitive

题目连接：

　　http://codeforces.com/problemset/problem/555/B

题目大意：

　　有n个岛屿（岛屿在一列上，可以看做是线性的，用来描述岛屿位置的是起点与终点），m个桥，给出每个岛屿的位置和桥的长度，问是否可以把n个岛屿连起来？

解题思路：

　　排序+贪心，对于n个岛屿，相邻的两个之间起点和端点可以转化为n-1个连接桥的长度区间，把区间升序排列。

　　对于m个桥升序排列，对于每一个桥枚举每个可以合法覆盖的区间，选取最优的，选取的时候满足L<bridge_length<R,L经是有序的了。我们只需选取R最小的那个，因为R越大，这个区间就能适应更多的桥。

　　本宝宝对于选取最优区间的时候采用了优先队列，并不是最优的处理方式，大家有好的办法可以留言告诉弱弱。

 #include <algorithm>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <queue>

 using namespace std;

 const int maxn = ;

 #define LL __int64

 struct bridge

 {

     LL val, id;

     bool operator < (const bridge &a) const

     {

         return val < a.val;

     }

 } Bri[maxn];

 struct island

 {

     LL r, l, id;

     bool operator < (const island &a) const

     {

         return l < a.l;

     }

 } Is[maxn];

 struct node

 {

     LL s, id;

     bool operator < (const node &a) const

     {

         return s > a.s;

     }

 };

 LL vis[maxn], n, m;

 bool solve ()

 {

     priority_queue <node>Q;//当前桥可以搭建成功的区间

     int l=;

     memset (vis, , sizeof(vis));

     for (int i=; i<m; i++)//对于每个桥选取最优的区间搭建

     {

         node nu;

         while (!Q.empty())

         {

             nu = Q.top();

             if (nu.s < Bri[i].val)

                 Q.pop();//删除队列中的不合法区间

             else

                 break;

         }

         while (Bri[i].val>=Is[l].l && Is[l].r >= Bri[i].val && l<n-)

         {

             nu.id = Is[l].id;

             nu.s = Is[l].r;

             Q.push (nu);//区间加进队列

             l ++;

         }

         if (Q.empty())

             continue;//没有合适的边，就继续循环加边

         nu = Q.top ();

         vis[nu.id] = Bri[i].id;//记录连接区间所对应的边

         Q.pop();

     }

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

         if (!vis[i])

             return false;

     return true;//所有区间都对应有边

 }

 int main ()

 {

     while (scanf ("%I64d %I64d", &n, &m) != EOF)

     {

         island pre, cur;

         LL i;

         scanf ("%I64d %I64d", &pre.l, &pre.r);

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

         {

             scanf ("%I64d %I64d", &cur.l, &cur.r);

             Is[i-].id = i;

             Is[i-].l = cur.l - pre.r;

             Is[i-].r = cur.r - pre.l;

             pre = cur;

         }

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

         {

             Bri[i].id = i+;

             scanf ("%I64d", &Bri[i].val);

         }

         sort (Is, Is+n-);

         sort (Bri, Bri+m);

         if (solve ())

         {

             printf ("Yes\n");

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

                 printf ("%I64d ", vis[i]);

             printf ("%I64d\n", vis[i]);

         }

         else

             printf ("No\n");

     }

     return ;

 }

巴特西

codeforces 555B Case of Fugitive

最新文章

热门文章