BestCoder3 1001 Task schedule(hdu 4907) 解题报告

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

题目意思：给出工作表上的 n 个任务，第 i 个任务需要 ti 这么长的时间（持续时间是ti ~ ti+1）来完成。有m 个询问，每个询问是一个数字q，表示q 时间上有一个非 n 个任务之外的任务请求。机器是按照工作表的任务时间来执行的，如果有空档时间，它会执行工作表之外的任务请求。

直接做，果断超时！1e5 * 2e5 ！！！（m次询问+q次遍历的最坏情况）

二分解决之～～～～一开始我不是只存储空闲时间啦，我还把工作表上要处理的n 个任务的时间都存在一起，导致写的二分不三不四啊～～～～= =

二分思想其实好容易理解，真正运用起来还是第一次啊～～～好好纪念纪念 ^_^

（1）这个是参考别人的，不过时间稍微用得有点多

Exe time :

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn = 2e5;

 int a[maxn], b[maxn];

 int main()

 {

     int T, n, m, ti, query;

     while (scanf("%d", &T) != EOF)

     {

         while (T--)

         {

             memset(a, , sizeof(a));

             memset(b, , sizeof(b));

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

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

             {

                 scanf("%d", &ti);

                 a[ti] = ;

             }

             int len = ;

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

             {

                 if (!a[i])

                     b[len++] = i;  // 把空余时间存储起来

             }

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

             {

                 scanf("%d", &query);

                 if (!a[query])

                     printf("%d\n", query);

                 else

                 {

                     int flag = ;

                     int l = , r = len-;

                     while (l <= r)

                     {

                         int mid = (l+r)/;

                         if (b[mid] == query)

                         {

                             printf("%d\n", b[mid]);

                             flag = ;

                             break;

                         }

                         else if (b[mid] < query)

                             l = mid+;

                         else if (b[mid] > query)

                             r = mid-;

                     }

                     if (!flag)

                         printf("%d\n", b[l]);

                 }

             }

         }

     }

     return ;

 }

(2) 我的改良版本（其实不需要把maxn，也就是2e5 个所有空闲时间都存起来啦，只要把原来n个任务中最大的时间，再+1的那个时间存起来即可！！！）

所以maxi + 1 就是这个意思啦。

Exe time :

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn = 2e5;

 int vis[maxn], b[maxn];

 int main()

 {

     int T, n, m, t, q;

     while (scanf("%d", &T) != EOF)

     {

         while (T--)

         {

             memset(vis, , sizeof(vis));

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

             int maxi = ;

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

             {

                 scanf("%d", &t);

                 maxi = max(maxi, t);

                 vis[t] = ;

             }

             int len = ;

             for (int i = ; i <= maxi+; i++)  // maxi+1表示n个任务中花费时间最长为maxi，假设遇到一个maxi/maxi+1的任务，那么这个任务执行时间就是maxi+1

             {

                 if (!vis[i])

                     b[len++] = i;

             }

             while (m--)

             {

                 scanf("%d", &q);

                 if (!vis[q])

                     printf("%d\n", q);

                 else

                 {

                     int l = , r = len-;

                     int flag = ;

                     while (l <= r)

                     {

                         int mid = (l+r)>>;

                         if (b[mid] == q)

                         {

                             flag = ;

                             printf("%d\n", b[mid]);

                             break;

                         }

                         else if (b[mid] > q)

                             r = mid-;

                         else if (b[mid] < q)

                             l = mid+;

                     }

                     if (!flag)

                         printf("%d\n", b[l]);

                 }

             }

         }

     }

     return ;

 }

巴特西

BestCoder3 1001 Task schedule(hdu 4907) 解题报告

最新文章

热门文章