UVa 637 Booklet Printing

题目描述在打印文档时通常按顺序打印第一页、第二页……但若要制作折叠小册子booklet\texttt{booklet}booklet打印顺序必须改变。一本折叠小册子每张纸包含四个页面正面两张、背面两张。将所有纸张按顺序堆叠后从中间对折页面顺序就会像普通书籍一样正确。例如一本444页的小册子只需111张纸正面包含第444页和第111页背面包含第222页和第333页。给定总页数nnnn≤100n \le 100n≤100要求生成每张纸正反面的打印顺序。若某些页面位置为空则输出Blank。若某张纸的正面或背面完全空白则不输出该面。输出按纸张编号升序先正面后反面。输入格式输入包含一个或多个测试用例每行一个正整数nnn以单独一行0表示结束。输出格式对于每个测试用例输出报告格式如样例所示。若某面完全空白则不输出该面。样例输入1 14 4 0输出Printing order for 1 pages: Sheet 1, front: Blank, 1 Printing order for 14 pages: Sheet 1, front: Blank, 1 Sheet 1, back: 2, Blank Sheet 2, front: 14, 3 Sheet 2, back: 4, 13 Sheet 3, front: 12, 5 Sheet 3, back: 6, 11 Sheet 4, front: 10, 7 Sheet 4, back: 8, 9 Printing order for 4 pages: Sheet 1, front: 4, 1 Sheet 1, back: 2, 3题目分析小册子打印的实质是将nnn个页码按特定顺序分配到若干张纸的正反面上使得最终堆叠对折后页码连续且正确。每张纸可容纳444个页码位置正面左侧、正面右侧、背面左侧、背面右侧。通常的排列方式为从外向内页码按降序分配在正面左侧和背面右侧按升序分配在正面右侧和背面左侧。参考代码采用构造法首先确定需要多少张纸然后按顺序填充正面右侧和背面左侧即内页的升序部分再从后向前填充正面左侧和背面右侧即外页的降序部分。最后输出时若某面完全空白则跳过。解题思路计算纸张数设纸张数为sheet_number满足4×sheet_number≥n4 \times \textit{sheet\_number} \ge n4×sheet_number≥n且4×(sheet_number−1)n4 \times (\textit{sheet\_number}-1) n4×(sheet_number−1)n即sheet_number⌈n/4⌉\textit{sheet\_number} \lceil n/4 \rceilsheet_number⌈n/4⌉。代码中用循环递增sheet_number直到4×sheet_number≥n4 \times \textit{sheet\_number} \ge n4×sheet_number≥n。初始化纸张结构每个纸张有四个位置front_left、front_right、back_left、back_right初始均为000表示空白。填充升序页码右侧和背面左侧对于第iii张纸iii从000开始正面右侧front_right赋值为2i12i12i1。若2i2≤n2i2 \le n2i2≤n则背面左侧back_left赋值为2i22i22i2。这样从左到右正面右侧依次为1,3,5,…1, 3, 5, \dots1,3,5,…背面左侧依次为2,4,6,…2, 4, 6, \dots2,4,6,…即填充了前2×sheet_number2 \times \textit{sheet\_number}2×sheet_number个页码。填充降序页码正面左侧和背面右侧若还有剩余页码即n2×sheet_numbern 2 \times \textit{sheet\_number}n2×sheet_number则从最后一张纸开始向前填充背面右侧back_right赋值为下一个未分配的页码从2×sheet_number12 \times \textit{sheet\_number}12×sheet_number1开始递增。若还有剩余则正面左侧front_left赋值为再下一个未分配的页码。更新纸张索引向前移动继续填充直到所有页码分配完毕。输出按纸张顺序输出每张纸的正面和背面若正面非全空。输出格式需严格遵循样例注意空格和标点。复杂度分析纸张数最多⌈100/4⌉25\lceil 100/4 \rceil 25⌈100/4⌉25因此算法常数级。时间复杂度O(1)O(1)O(1)空间复杂度O(1)O(1)O(1)。代码实现// Booklet Printing// UVa ID: 637// Verdict: Accepted// Submission Date: 2016-08-26// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structsheet{intfront_left,front_right,back_left,back_right;};intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);sheet sheets[100];intn;while(cinn,n){memset(sheets,0,sizeof(sheets));intsheet_number0;do{sheets[sheet_number].front_right2*sheet_number1;if(2*sheet_number2n)sheets[sheet_number].back_left2*sheet_number2;sheet_number;}while(4*sheet_numbern);inttotal_sheetssheet_number,total_pages2*sheet_number;while(total_pagesn){sheets[total_sheets-1].back_righttotal_pages1;total_pages;if(total_pagesn){sheets[total_sheets-1].front_lefttotal_pages1;total_pages;}total_sheets--;}coutPrinting order for n pages:\n;for(inti0;isheet_number;i){coutSheet i1, front: ;if(sheets[i].front_left0)coutBlank;elsecoutsheets[i].front_left;cout, sheets[i].front_right\n;if(sheets[i].back_left0sheets[i].back_right0)continue;else{coutSheet i1, back : ;coutsheets[i].back_left, ;if(sheets[i].back_right0)coutBlank\n;elsecoutsheets[i].back_right\n;}}}return0;}总结本题通过构造法直接生成小册子打印顺序无需复杂的搜索或模拟。关键在于理解每张纸正反面的页码排列规律内页按升序填充右侧外页按降序填充左侧。代码利用数组存储每个位置按步骤填充后再统一输出逻辑清晰。输出时注意处理完全空白的面避免多余输出。此方法适用于nnn不超过100100100的小规模数据且效率极高。