AOJ : 0147 - 福縞軒 (Fukushimaken)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0147&lang=jp
お客さんの待ち行列のシミュレート問題

アルゴリズム

実装するだけです.
頭こんがらがるときは, 関数とかに分けつつ実装すると結構簡単です.
とくに説明なし.

プログラム

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int ans[100];

class G{
public:
  int id,n,a,d; //グループ番号,人数,到着時刻,食事時間

  G(int i){
    id = i;
    n = (i % 5 == 1 ? 5 : 2);
    a = 5 * i;
    d = 17 * (i % 2) + 3 * (i % 3) + 19;
  }
};

//n人連続で席を確保できる場所を返す
int indexOfSeat(int *seat,int n){
  int count = 0;

  for(int i=0;i<17;i++){
    if(!seat[i]){
      count++;
      if(count == n) return i - n + 1;
    }
    else{
      count = 0;
    }
  }

  return -1;
}

void solve(void){
  vector<G> v; //待ち行列
  for(int i=0;i<100;i++) v.push_back(G(i));

  int time = 0; //現在の時刻
  int seat[17]; //席情報
  memset(seat,0,sizeof(seat));

  while(!v.empty()){
    while(!v.empty() && v[0].a<=time){
      int idx = indexOfSeat(seat,v[0].n);
      if(idx != -1){
        for(int i=idx;i<idx+v[0].n;i++) seat[i] = v[0].d;
        ans[v[0].id] = time - v[0].a;
        v.erase(v.begin());
      }
      else{
        break;
      }
    }

    time++;
    for(int i=0;i<17;i++) if(seat[i] > 0) seat[i]--;
  }
}

int main(void){
  solve();

  int n;
  while(cin>>n) cout<<ans[n]<<endl;

  return 0;
}