Book Replacement

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem B

[解説]

シミュレーション。

[サンプルプログラム]

001 #include<iostream>
002 #include<queue>
003 #include<vector>
004 using namespace std;
005 
006 class Student{
007     public:
008     queue<int> requests;
009     Student(){}
010     
011     int getRequest(){
012         int r = requests.front(); requests.pop();
013         return r;
014     }
015 };
016 
017 class Storeroom{
018     public:
019     int capacity, ndesk;
020     vector<vector<int> > buffer;
021     
022     Storeroom(){}
023     Storeroom(int d, int c): ndesk(d), capacity(c){
024         buffer.resize(d+1);
025         for ( int i = 1; i <= 100; i++ ){
026             buffer[d].push_back(i);
027         }
028     }
029     
030     int take( int requested, int &cost ){
031         for ( int d = 0; d <= ndesk; d++ ){
032             for ( int i = 0; i < buffer[d].size(); i++ ){
033                 if ( buffer[d][i] == requested ){
034                     cost += (d+1);
035                     int book = buffer[d][i];
036                     buffer[d].erase( buffer[d].begin() + i );
037                     return book;
038                 }
039             }
040         }
041     }
042     
043     bool isFull(int d){
044         return buffer[d].size() >= capacity;
045     }
046     
047     void put(int d, int book, int &cost){
048         buffer[d].push_back(book);
049         cost += (d+1);
050     }
051     
052     int getNonFullDesk(){
053         for ( int d = 1; d < ndesk; d++ ){
054             if ( buffer[d].size() < capacity ) return d;
055         }
056         return ndesk;
057     }
058     
059     int takePassive(int &cost){
060         int tmp = buffer[0][0];
061         buffer[0].erase( buffer[0].begin() + 0 );
062         cost++;
063         return tmp;
064     }
065 };
066 
067 queue<Student> students;
068 Storeroom storeroom;
069 
070 int simulate(){
071     int cost = 0;
072     Student st;
073     int requested, desk, target;
074     
075     while( !students.empty() ){
076         st = students.front(); students.pop();
077         requested = st.getRequest();
078         
079         target = storeroom.take(requested, cost);
080         
081         if ( !storeroom.isFull(0) ) {
082             storeroom.put(0, target, cost);
083         } else {
084             desk = storeroom.getNonFullDesk();
085             storeroom.put(desk, target, cost);
086             
087             target = storeroom.takePassive(cost);
088             desk = storeroom.getNonFullDesk();
089             storeroom.put(desk, target, cost);
090             
091             target = storeroom.take(requested, cost);
092             storeroom.put(0, target, cost);
093         }
094         
095         if ( st.requests.size() ) students.push(st);
096     }
097     
098     return cost;
099 }
100 
101 bool input(){
102     int m, c, n, k;
103     cin >> m >> c >> n;
104     if ( m == 0 && c == 0 && n == 0 ) return false;
105     storeroom = Storeroom( m, c );
106     students = queue<Student>();
107     
108     for ( int i = 0; i < n; i++ ){
109         cin >> k;
110         Student st;
111         for ( int j = 0; j < k; j++ ){
112             int id; cin >> id;
113             st.requests.push(id);
114         }
115         students.push(st);
116     }
117     
118     return true;
119 }
120 
121 main(){
122     while(input()) cout << simulate() << endl;
123 }