题目描述
在打印文档时，通常按顺序打印第一页、第二页……但若要制作折叠小册子（booklet\texttt{booklet}booklet），打印顺序必须改变。一本折叠小册子每张纸包含四个页面：正面两张、背面两张。将所有纸张按顺序堆叠后，从中间对折，页面顺序就会像普通书籍一样正确。例如，一本444页的小册子只需111张纸：正面包含第444页和第111页，背面包含第222页和第333页。
给定总页数nnn（n≤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）赋值为2i+12i+12i+1。 - 若2i+2≤n2i+2 \le n2i+2≤n，则背面左侧（
back_left）赋值为2i+22i+22i+2。
这样从左到右，正面右侧依次为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个页码。
- 正面右侧（
填充降序页码（正面左侧和背面右侧）：若还有剩余页码（即n>2×sheet_numbern > 2 \times \textit{sheet\_number}n>2×sheet_number），则从最后一张纸开始向前填充：
- 背面右侧（
back_right）赋值为下一个未分配的页码（从2×sheet_number+12 \times \textit{sheet\_number}+12×sheet_number+1开始递增）。 - 若还有剩余，则正面左侧（
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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;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(cin>>n,n){memset(sheets,0,sizeof(sheets));intsheet_number=0;do{sheets[sheet_number].front_right=2*sheet_number+1;if(2*sheet_number+2<=n)sheets[sheet_number].back_left=2*sheet_number+2;sheet_number++;}while(4*sheet_number<n);inttotal_sheets=sheet_number,total_pages=2*sheet_number;while(total_pages<n){sheets[total_sheets-1].back_right=total_pages+1;total_pages++;if(total_pages<n){sheets[total_sheets-1].front_left=total_pages+1;total_pages++;}total_sheets--;}cout<<"Printing order for "<<n<<" pages:\n";for(inti=0;i<sheet_number;i++){cout<<"Sheet "<<i+1<<", front: ";if(sheets[i].front_left==0)cout<<"Blank";elsecout<<sheets[i].front_left;cout<<", "<<sheets[i].front_right<<'\n';if(sheets[i].back_left==0&&sheets[i].back_right==0)continue;else{cout<<"Sheet "<<i+1<<", back : ";cout<<sheets[i].back_left<<", ";if(sheets[i].back_right==0)cout<<"Blank\n";elsecout<<sheets[i].back_right<<'\n';}}}return0;}总结
本题通过构造法直接生成小册子打印顺序，无需复杂的搜索或模拟。关键在于理解每张纸正反面的页码排列规律：内页按升序填充右侧，外页按降序填充左侧。代码利用数组存储每个位置，按步骤填充后再统一输出，逻辑清晰。输出时注意处理完全空白的面，避免多余输出。此方法适用于nnn不超过100100100的小规模数据，且效率极高。
