Problem 0192 : Tsuruga Parking

Tsuruga Parking
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0192

• 問題概要

二段式の駐車場が複数ある。
１０分ごとに、車がくる。
車それぞれ駐車したい時間をもっている。
下の車がまだいるとき上の車は出れない。
決められた法則にしたがって車を駐車していくとき、どのような順番で車は外に出ますか？

• 解法

頑張って書く。
v12のシミュレーションに比べて比較的書きやすかった。
っていうか、最近実装ゲーがたのしい。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

int cnt;
bool first;
const int INF = 1000000;

class Park{
public:
  int leftTime[2];
  int ID[2];
  bool car[2];

  Park(){
    rep(i, 2)car[i] = false;
  }
  
  void next(){ 
    rep(i, 2){
      if(car[i]){
	leftTime[i]--;
      }
    }
    rep(i, 2){
      if(car[i] && leftTime[i] <= 0){
	if(first){
	  first = false;
	}
	else cout << ' ';
	cnt++;
	cout << ID[i]+1;
	car[i] = false;
      }
      if(car[i])return;
    }
    return;
  }
  
  void put(int id, int time){
    int tmp = 1;
    if(car[1])tmp = 0;
    car[tmp] = true;
    ID[tmp] = id;
    leftTime[tmp] = time;
    return;
  }

  int diff(int time){
    return abs(time - leftTime[1]);
  }
};
  
main(){
  
  int n, m;
  while(cin >> m >> n){
    if(m + n == 0)break;
    Park p[m];
    first = true;
    int time = 0, id = 0;
    cnt = 0;
    queue<int> ID, Data;
    while(cnt < n){
      if(id < n && time == 0){
	int tmp;
	cin >> tmp;
	ID.push(id);
	Data.push(tmp);
	id++;
      }

      while(!ID.empty()){
	int next = -1;
	rep(i, m){
	  if(p[i].car[1])continue;
	  next = i;
	  break;
	}
	if(next != -1){
	  p[next].put(ID.front(), Data.front());
	  ID.pop();Data.pop();
	  continue;
	}
	
	int mini = INF, nTime = Data.front();
	rep(i, m){
	  if(p[i].car[0])continue;
	  if(p[i].leftTime[1] < nTime)continue;
	  if(mini > p[i].diff(nTime)){
	    mini = p[i].diff(nTime);
	    next = i;
	  }
	}
	if(next != -1){
	  p[next].put(ID.front(), Data.front());
	  ID.pop();Data.pop();
	  continue;
	}
	
	rep(i, m){
	  if(p[i].car[0])continue;
	  if(mini > p[i].diff(nTime)){
	    mini = p[i].diff(nTime);
	    next = i;
	  }
	}
	if(next != -1){
	  p[next].put(ID.front(), Data.front());
	  ID.pop();Data.pop();
	  continue;
	}
	break;
      }
      time++;
      if(time == 10)time = 0;
      rep(i, m)p[i].next();
    }
    cout << endl;
  }	  
}