Book Replacement
2007.08.24 22:21 ACM/ICPC 2005
[問題] 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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |