BYR Achieve · 镜像论坛

这道题提交很少我觉得一定是因为题目太长了。。当时并没有写完，下来自己也梳理了很久，感觉讨论得很复杂，不知道有没有什么好的方法。先说说题目吧： ================================================================= 故事背景是开发外星球，这个星球被划分成了从0开始编号的块探测器会执行两种任务： * 探测任务输入两个正整数，分别表示计划开始的地块编号和携带的资源数量起点编号为 0 < x <= 5*10^8, 资源数量为 0 < x <= 1000 1 探测器将从计划开始的地块开始按编号寻找第一个没有探测过的地块 2 探测器顺次进行探测，每勘探一块地块消耗一个单位的资源 3 如果资源用尽，或者到达了一个已经探测过的地块，则返回执行下一次任务输出实际探测的起点编号和终点编号 * 清理任务输入是一个负数，表示将对应正数的地块重置成未探测的状态 - 5*10^8 <= y < 0 无输出任务数量不超过 10^5 ================================================================== 直接用数组模拟的话内存会超，就尝试用map<int, int>来存储连续的勘探过的地块编号（s,t) 感觉维护上的讨论非常复杂且笨拙，所以上论坛来请教一下。。目前我调试出的一个版本（说不定有bug）那么长: #include <cstdio> #include <map> using namespace std; map<int, int> dect; void doTask(int st, int sr) { int s = st, t = st + sr - 1; map<int, int>::iterator it, it0, it1; for(it0 = it = dect.begin(); it != dect.end(); it++) { if(it->second > s) //寻找第一个超过s的段 { printf("Find (%d,%d)(%d,%d)\n",it0->first, it0->second,it->first, it->second); break; } it0 = it; } if(it == dect.end()) // 所有的ed都小于或等于s { if(it0 == dect.end() || it0->second + 1 < s) // 前一个足够远 { printf("1 New (%d,%d)\n", s, t); dect.insert(pair<int, int>(s, t)); } else // 与前一个合并 { printf("2 Longer (%d,%d)->(%d,%d)\n", it0->first, it0->second, it0->first, it0->second + sr); s = it0->second + 1; t = s + sr - 1; it0->second = t; } } else // 某一个ed > s { if(s >= it->first) //延长这一段 { s = it->second + 1; t = s + sr - 1; //查看下一段 it1 = it; it ++; if(it == dect.end() || it->first > t + 1) // 后一个足够远 { printf("3 Longer (%d,%d)->(%d,%d)\n", it1->first, it1->second, it1->first, t); it1->second = t; } else // 与后一个合并 { printf("4 MergeTwo (%d,%d)+(%d,%d)->(%d,%d)\n", it1->first, it1->second, it->first, it->second ,it1->first, it->second); t = it->first - 1; it1->second = it->second; dect.erase(it); } } else // 落在前面 { if(it0 != it) { if(it0->second + 1 < s) // 前一个足够远 { if(t >= it->first - 1) { printf("5 preLonger (%d,%d)->(%d,%d)\n",it->first, it->second, s, it->second); t = it->first - 1; dect.insert(pair<int, int>(s, it->second)); dect.erase(it); } else { printf("6 New (%d,%d)\n", s, t); dect.insert(pair<int, int>(s, t)); } } else // 与前一个合并 { s = it0->second + 1; t = s + sr - 1; if(t >= it->first - 1) { printf("7 MergeTwo (%d,%d)+(%d,%d)->(%d,%d)\n", it0->first, it0->second, it->first, it->second, it0->first, it->second); t = it->first - 1; it0->second = it->second; dect.erase(it); } else { printf("8 Longer (%d,%d)->(%d,%d)\n", it0->first, it0->second, it0->first, t); it0->second = t; } } } else // it0 == it { if(it->first > t + 1) // 后一个足够远 { printf("9 New (%d,%d)\n", s, t); dect.insert(pair<int, int>(s, t)); } else // 与后一个合并 { printf("10 Longer (%d,%d)->(%d,%d)\n", it->first, it->second, s, it->second); t = it->first - 1; dect.insert(pair<int, int>(s, it->second)); dect.erase(it); } } } } printf("%d %d\n", s, t); } void doClean(int p) { map<int, int>::iterator it; for(it = dect.begin(); it != dect.end(); it++) { if(it->second >= p && it->first <= p) //包含p的段 break; } if(it == dect.end()) return; if(it->second == it->first) { dect.erase(it); } else if(it->second == p) { it->second --; } else if(it->first == p) { dect.insert(pair<int, int>(p + 1, it->second)); dect.erase(it); } else { dect.insert(pair<int, int>(p + 1, it->second)); it->second = p - 1; } } void show() { map<int, int>::iterator it; for(it = dect.begin(); it != dect.end(); it++) { printf("(%d,%d) ",it->first, it->second); } printf("\n\n"); } int main() { int n, i, st, sr; while(scanf("%d", &n) != EOF) { dect.clear(); for(i = 0; i < n; i++) { scanf("%d", &st); if(st > 0) { scanf("%d", &sr); doTask(st, sr); } else if(st < 0) { doClean(-st); } else { // No 0 } show(); } } return 0; }

预选赛E题Liquid