XDOJ総合プログラミング練習173チケット購入システム
テーマの内容
見出し
チケット購入システム
カテゴリ
統合
時間の制限
1S
メモリ制限
256Kb
問題の説明
鉄道切符購入システムの簡単な座席割り当てアルゴリズムを実現して、1両の車両の座席割り当てを処理してください.1両に20列、各5席があると仮定します.便宜上、私たちは1~100ですべての座席番号をあげます.1列目は1~5番、2列目は6~10番で、順番に類推して、20列目は96~100番です.切符を買う時、一人で1枚以上の切符を買うことができて、最大5枚を超えません.これらの切符が同じ列の番号の隣の席に配置できる場合は、番号の一番小さい隣の席に配置する必要があります.そうでない場合は、番号が最も小さいいくつかの空席に配置する必要があります(隣接するかどうかを考慮しません).当初は乗車券がすべて購入されていなかったと仮定し、現在いくつかの購入指令が与えられていますので、これらの指令を処理して、購入結果を出力してください.例えば、一度に2,5,4,2枚のチケットを購入した場合、1)2枚のチケットを購入し、座席1,2を取得します.2)チケットを5枚購入し、座席6~10を得る.3)チケットを4枚購入し、座席11~14を得る.4)チケットを2枚購入し、座席3、4をもらう.
説明の入力
入力は2行で構成されています.第1行は、チケット購入命令の数を表す整数nを含み、1≦n≦100である.2行目はn個の整数を含み、各整数pは1から5の間で、購入する票数を表し、隣接する2つの整数の間に1つのスペースで区切られ、すべての購入票数の和は100を超えない.
出力の説明
n行を出力し、各行に1つのチケット購入命令の処理結果を対応させる.すなわち、チケット購入指令pについて、p枚のチケットの番号を小さい順に出力する.
入力サンプル
4 2 5 4 2
出力サンプル
1 2 6 7 8 9 10 11 12 13 14 3 4
構想
全体的な考え方.
明らかに、この問題は私たちが直接切符購入指令の運行をシミュレートすればいい.入力が5未満の場合、空き座席が需要数以上を満たす最初の列を見つけ、下書きを計算して出力をマークすれば である.入力が5に等しいとき、空き座席が5に等しい最初の列を見つけ、下付きラベルを計算して出力をマークすれば である.
各列が左揃えになっているので、各列の既売席が必ず連続していれば、空き席も必ず連続しています以上の2点が満たされない場合、この需要が分配されるまで縫い針を見て、同時に下付きを計算して を出力する.
私たちがすべきことはは、座席が で販売されているかどうかを20*5の大きさの配列で示す.は長さ20の配列で各列の空き座席数 を記録する.
コード#コード#
私が書くのが少し煩わしい感じがします...例えばop==1を単独で考えなくてもいい場合(例えばgotoを使わずコードをより簡潔に理解できるように)もっと良い考えがあれば、コメントエリアにアドバイスを残してほしいです.
見出し
チケット購入システム
カテゴリ
統合
時間の制限
1S
メモリ制限
256Kb
問題の説明
鉄道切符購入システムの簡単な座席割り当てアルゴリズムを実現して、1両の車両の座席割り当てを処理してください.1両に20列、各5席があると仮定します.便宜上、私たちは1~100ですべての座席番号をあげます.1列目は1~5番、2列目は6~10番で、順番に類推して、20列目は96~100番です.切符を買う時、一人で1枚以上の切符を買うことができて、最大5枚を超えません.これらの切符が同じ列の番号の隣の席に配置できる場合は、番号の一番小さい隣の席に配置する必要があります.そうでない場合は、番号が最も小さいいくつかの空席に配置する必要があります(隣接するかどうかを考慮しません).当初は乗車券がすべて購入されていなかったと仮定し、現在いくつかの購入指令が与えられていますので、これらの指令を処理して、購入結果を出力してください.例えば、一度に2,5,4,2枚のチケットを購入した場合、1)2枚のチケットを購入し、座席1,2を取得します.2)チケットを5枚購入し、座席6~10を得る.3)チケットを4枚購入し、座席11~14を得る.4)チケットを2枚購入し、座席3、4をもらう.
説明の入力
入力は2行で構成されています.第1行は、チケット購入命令の数を表す整数nを含み、1≦n≦100である.2行目はn個の整数を含み、各整数pは1から5の間で、購入する票数を表し、隣接する2つの整数の間に1つのスペースで区切られ、すべての購入票数の和は100を超えない.
出力の説明
n行を出力し、各行に1つのチケット購入命令の処理結果を対応させる.すなわち、チケット購入指令pについて、p枚のチケットの番号を小さい順に出力する.
入力サンプル
4 2 5 4 2
出力サンプル
1 2 6 7 8 9 10 11 12 13 14 3 4
構想
全体的な考え方.
明らかに、この問題は私たちが直接切符購入指令の運行をシミュレートすればいい.
各列が左揃えになっているので、各列の既売席が必ず連続していれば、空き席も必ず連続しています
私たちがすべきことは
コード#コード#
私が書くのが少し煩わしい感じがします...例えばop==1を単独で考えなくてもいい場合(例えばgotoを使わずコードをより簡潔に理解できるように)もっと良い考えがあれば、コメントエリアにアドバイスを残してほしいです.
#include
using namespace std;
int main(){
bool ticket[20][5] = {
false};// , false ,
int cnt[20];//count,
for(int i = 0;i < 20;i++)
cnt[i] = 5;
int n, op, t;// , ,
cin >> n;
for(int i = 0;i < n;i++){
cin >> op;
if(op == 1){
for(int a = 0;a < 20;a++)
for(int b = 0;b < 5;b++)
if(ticket[a][b] == false){
//
ticket[a][b] = true;//
cout << a*5+b+1 << endl;//
cnt[a]--;// 1
goto END;//
}
}
if(op < 5){
for(int col = 0;col < 20;col++){
if(cnt[col] >= op){
//
for(int b = 0;b < 5;b++){
if(ticket[col][b] == false){
//
for(int bb = 0;bb < op;bb++){
ticket[col][b+bb] = true;//
cnt[col]--;// 1
cout << col*5+b+bb+1 << " ";//
}
cout << endl;//
goto END;//
}
}
}
}
goto EXCP;// ,
}
if(op == 5){
//
for(int col = 0;col < 20;col++){
if(cnt[col] == 5){
for(int b = 0;b < 5;b++){
ticket[col][b] = true; //
cout << col*5+b+1 << " ";//
}
cnt[col] = 0;//
cout << endl;//
goto END;//
}
}
goto EXCP;// ,
}
EXCP://
t = op;
for(int a = 0;a < 20;a++)
for(int b = 0;b < 5;b++){
if(ticket[a][b] == false){
//
ticket[a][b] = true;//
cout << a*5+b+1 << " ";//
t--;//
cnt[a]--;// 1
}
if(t == 0){
//
cout << endl;//
goto END;//
}
}
END:;// ;)
}
}