电梯调度算法 Elevator algorithm

elevator.cc

#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;
}