Last active
December 31, 2018 09:02
-
-
Save LeeReindeer/95efbc79b18636236dca4625bb5b83d5 to your computer and use it in GitHub Desktop.
电梯调度算法 Elevator algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <cstdlib> | |
#include <iostream> | |
using namespace std; | |
/** | |
* @brief 电梯调度算法 | |
* @author LeeReindeer | |
* 试着模仿 ACM 竞赛题目的格式: | |
* 假设磁盘柱面编号由外向内递增,从0开始编号 | |
* 输入格式: | |
* 第一行分别为:磁盘的柱面总数N,当前处于的柱面cur,当前移动的方向dir(1表示向内,-1表示向外) | |
* 第二行为请求访问的柱面个数n | |
* 接下来访问柱面的次序。 | |
* 输出格式: | |
* 访问柱面的次序和移动臂移动的柱面总数。 | |
* 输入样例: | |
* 200 50 1 | |
* 7 | |
* 150 30 190 20 100 55 90 | |
* 输出样例: | |
* 55 90 100 150 190 30 20 | |
* 310 | |
*/ | |
const int maxn = 1000; | |
int N, n; | |
int order[maxn], ans[maxn]; | |
int cylinder[maxn] = {-1}; | |
void print_order(int a[]) { | |
for (int i = 0; i < n; i++) { | |
cout << a[i] << " "; | |
} | |
cout << endl; | |
} | |
/** | |
* @brief find the index of current cylinder, | |
* return order's index if find, else return -1 | |
*/ | |
int find_same(int cur) { | |
int L = 0, R = n - 1; | |
while (R - L >= 0) { | |
int m = (L + R) / 2; | |
if (order[m] == cur && cylinder[order[m]] != 1) { | |
return m; | |
} else if (order[m] > cur) | |
R = m - 1; | |
else | |
L = m + 1; | |
} | |
return -1; | |
// todo use binary search to find greater or less index | |
// not find same | |
// *ok = 0; | |
// if (dir == 1) | |
// return L; // return index of the one just greater then current | |
// else | |
// return R; | |
} | |
int find_greater_less(int current, int dir) { | |
if (dir == 1) { //向内 | |
for (int i = 0; i < n; i++) { | |
if (current < order[i] && cylinder[order[i]] != 1) { | |
return i; | |
} | |
} | |
} else if (dir == -1) { //向外 | |
for (int i = n - 1; i >= 0; i--) { | |
if (current > order[i] && cylinder[order[i]] != 1) { | |
return i; | |
} | |
} | |
} | |
return -1; | |
} | |
int main() { | |
int cur, dir; | |
cin >> N >> cur >> dir >> n; | |
for (int i = 0; i < n; i++) { | |
cin >> order[i]; | |
} | |
sort(order, order + n); | |
int sum = 0, cur_order = 0; | |
while (cur_order < n) { | |
int index = find_same(cur); | |
if (index != -1) { // find same | |
cylinder[order[index]] = 1; | |
ans[cur_order++] = order[index]; | |
} else { | |
index = find_greater_less(cur, dir); // find greater or less | |
if (index != -1) { | |
sum += (abs(order[index] - cur)); | |
cylinder[order[index]] = 1; | |
ans[cur_order++] = order[index]; | |
cur = order[index]; // change cur | |
} else { | |
// change dir | |
dir = -dir; | |
} | |
} | |
} | |
print_order(ans); | |
cout << sum << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment