問題描述
請實(shí)現(xiàn)一個(gè)鐵路購票系統(tǒng)的簡單座位分配算法,來處理一節(jié)車廂的座位分配辟狈。
假設(shè)一節(jié)車廂有20排遏考、每一排5個(gè)座位立润。為方便起見,我們用1到100來給所有的座位編號,第一排是1到5號,第二排
是6到10號,依次類推,第20排是96到100號喊儡。
購票時(shí),一個(gè)人可能購一張或多張票,最多不超過5張输瓜。如果這幾張票可以安排在同一排編號相鄰的座位,則應(yīng)該安
排在編號最小的相鄰座位。否則應(yīng)該安排在編號最小的幾個(gè)空座位中(不考慮是否相鄰)猿规。
假設(shè)初始時(shí)車票全部未被購買,現(xiàn)在給了一些購票指令,請你處理這些指令。
輸入格式
輸入的第一行包含一個(gè)整數(shù)n,表示購票指令的數(shù)量宙橱。
第二行包含n個(gè)整數(shù),每個(gè)整數(shù)p在1到5之間,表示要購入的票數(shù),相鄰的兩個(gè)數(shù)之間使用一個(gè)空格分隔姨俩。
輸出格式
輸出n行,每行對應(yīng)一條指令的處理結(jié)果。
對于購票指令p,輸出p張車票的編號,按從小到大排序
樣例輸入
4
2 5 4 2
樣例輸出
1 2
6 7 8 9 10
11 12 13 14
3 4
樣例說明
- 購2張票,得到座位1师郑、2环葵。
2) 購5張票,得到座位6至10。
3) 購4張票,得到座位11至14宝冕。
4) 購2張票,得到座位3张遭、4。
評測用例規(guī)模與約定
對于所有評測用例,1 ≤ n ≤ 100,所有購票數(shù)量之和不超過100地梨。
思路解析
思路一：因?yàn)樵摴?jié)車廂有20排菊卷，每排5個(gè)缔恳，所以很容易想到建立一個(gè)名為zw， 20 × 5 的數(shù)組洁闰，如果座位上已經(jīng)有人了歉甚，則置“該座位”的值為1,即讓zw[i][j]=1(座位號為 i5+j+1* 上面已經(jīng)有人了);
思路二：我們?nèi)绻O(shè)置一個(gè) 20 * 6 的數(shù)組，每行多出來的一個(gè)位置用來存放該行剩余的空座位
比較：第一種思路實(shí)現(xiàn)起來比較繁瑣扑眉，而且效率低于第二種纸泄。因?yàn)槿绻阍O(shè)置 20 * 5 的數(shù)組，則每次分配座位的時(shí)候腰素，都要從第0排的第0個(gè)位置開始掃描聘裁，即要兩個(gè)for循環(huán)，在內(nèi)循環(huán)中還要實(shí)現(xiàn)if（zw[i][j]==0）,即若等于9,則說明該座位空弓千，即要統(tǒng)計(jì)出該行的空余位置衡便，然后再決定是否分配;第二種思路相對于第一種思路減少了統(tǒng)計(jì)該行空余位置的步驟，因?yàn)槲覀円呀?jīng)在數(shù)組中記錄下來了计呈，這樣實(shí)現(xiàn)簡單砰诵，方便。
注：
我們要把題目理解透徹捌显，據(jù)題意而知茁彭，不可能出現(xiàn) |0|1|1|0|0| 的情況;**
要注意數(shù)組下標(biāo)和座位號之間的關(guān)系，每行數(shù)組下標(biāo)是從0開始扶歪，每行座位下標(biāo)是從1開始
源碼
package Second;
/**
* Created by fxr on 16-9-12.
*/
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int count[] = new int[100];
for (int i = 0; i < N; i++) {
count[i] = sc.nextInt();
}
int zw[][] = new int[20][6];
for (int i = 0; i < zw.length; i++) {
zw[i][5] = 5;
}
for (int i = 0; i < N; i++) {
int temp = count[i];
boolean flag = false;//記錄連續(xù)分配是否成功
for (int j = 0; j < zw.length; j++) {
int res = zw[j][5];//記錄該行的剩余空位
if (res >= temp) {
int start = 5 - res;//記錄從該行的什么位置開始分配
zw[j][5] -= count[i];
flag = true;
for (int k = start; k < start + count[i]; k++) {
System.out.print(j * 5 + k + 1 + " ");
}
System.out.println();
break;
}
}
if (!flag) {//記錄連續(xù)分配未成功
for (int j = 0; j < zw.length; j++) {
int res = zw[j][5];
if (res > 0) {
System.out.print(j * 5 + 5 - res + 1 + " ");
zw[j][5 - res] = 1;
zw[j][5] -= temp;
temp--;
}
if(temp==0){
break;
}
}
System.out.println();
}
}
}
}
