首页 > 代码库 > BestCoder3 1001 Task schedule(hdu 4907) 解题报告
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 : 
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 2e5; 8 int a[maxn], b[maxn]; 9 10 int main()11 {12 int T, n, m, ti, query;13 while (scanf("%d", &T) != EOF)14 {15 while (T--)16 {17 memset(a, 0, sizeof(a));18 memset(b, 0, sizeof(b));19 scanf("%d%d", &n, &m);20 for (int i = 0; i < n; i++)21 {22 scanf("%d", &ti);23 a[ti] = 1;24 }25 int len = 0;26 for (int i = 1; i <= maxn; i++)27 {28 if (!a[i])29 b[len++] = i; // 把空余时间存储起来30 }31 for (int i = 0; i < m; i++)32 {33 scanf("%d", &query);34 if (!a[query])35 printf("%d\n", query);36 else37 {38 int flag = 0;39 int l = 0, r = len-1;40 while (l <= r)41 {42 int mid = (l+r)/2;43 if (b[mid] == query)44 {45 printf("%d\n", b[mid]);46 flag = 1;47 break;48 }49 else if (b[mid] < query)50 l = mid+1;51 else if (b[mid] > query)52 r = mid-1;53 }54 if (!flag)55 printf("%d\n", b[l]);56 }57 }58 }59 }60 return 0;61 }
(2) 我的改良版本（其实不需要把maxn，也就是2e5 个所有空闲时间都存起来啦，只要把原来n个任务中最大的时间，再+1的那个时间存起来即可！！！）
所以maxi + 1 就是这个意思啦。
Exe time : 
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 2e5; 8 int vis[maxn], b[maxn]; 9 10 int main()11 {12 int T, n, m, t, q;13 while (scanf("%d", &T) != EOF)14 {15 while (T--)16 {17 memset(vis, 0, sizeof(vis));18 scanf("%d%d", &n, &m);19 int maxi = 1;20 for (int i = 1; i <= n; i++)21 {22 scanf("%d", &t);23 maxi = max(maxi, t); 24 vis[t] = 1;25 }26 int len = 0;27 for (int i = 1; i <= maxi+1; i++) // maxi+1表示n个任务中花费时间最长为maxi，假设遇到一个maxi/maxi+1的任务，那么这个任务执行时间就是maxi+1 28 {29 if (!vis[i])30 b[len++] = i;31 }32 while (m--)33 {34 scanf("%d", &q);35 if (!vis[q])36 printf("%d\n", q);37 else38 {39 int l = 0, r = len-1;40 int flag = 0;41 while (l <= r)42 {43 int mid = (l+r)>>1;44 if (b[mid] == q)45 {46 flag = 1;47 printf("%d\n", b[mid]);48 break;49 }50 else if (b[mid] > q)51 r = mid-1;52 else if (b[mid] < q)53 l = mid+1;54 }55 if (!flag)56 printf("%d\n", b[l]);57 }58 }59 }60 }61 return 0;62 }
BestCoder3 1001 Task schedule(hdu 4907) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。