2017年蓝桥杯C组真题及解析
01 贪吃蛇长度 数数 -> 输入+字符判断+计数
标题：贪吃蛇长度
+-------------------------------------------------+
||
|---|
|# # #|
|# # #|
|# #### # #|
|# # # # #|
|######@### # #|
|# #### # #|
|# # # # #|
|####@#######@### # #|
|# # # # #|
|T ##### # # # ##|
|# # ### ### ##|
|################ # # ####|
|# # # #|
|############## #######@##########|
|# ###|
|###########################|
+-------------------------------------------------+ 小明在爷爷的私人收藏馆里找到一台老式电脑。居然没有图形界面，只能用控制台编程。经过小明的一阵摸索，神奇地设计出了控制台上的贪食蛇游戏。
如上图，是游戏时画面截图。
其中，H表示蛇头，T表示蛇尾。#表示蛇的身体，@表示身体交叉重叠的地方。
你能说出现在的贪吃蛇长度是多少吗？
其实，只要数出#的数目算1，数出@的数目，算2，再加上头尾各算1就计算好了。
人工数一下？太累眼睛了，聪明的你为什么不让计算机帮忙呢？
本题的要求就是： 请填写上图中贪食蛇的长度是多少？
注意：需要提交的是一个整数，不要添加任何多余内容（比如说明或注释） #include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int ans=0;
for (int i = 0; i < 20; ++i) {
for (int j = 0; j < 51; ++j) {
char c;
scanf("%c",&c);//璇诲叆瀛楃锛岃繘琛岀粺璁?
if(c=='#')ans++;
if(c=='@')ans+=2;
}
}
printf("%d",ans+2);
return 0;
}输出结果：190
02 兴趣小组 文件读取+set的运用
标题：兴趣小组
A.txt
A.txt
旨在充实同学们的课余文化生活, 某高校学生会下属三个兴趣小组. 该高校学生会将这三个兴趣小组统称为A组、B组与C组. 各兴趣小组的学生信息可在[A.txt]、[B.txt]及[C.txt]文件中查看. 其中每个文件都记录了参与者的学号信息.
为了解决工作中的一个问题，请问我们想了解同时加入了A组和B组但未加入C组的同学共有多少
请你统计该数字并通过浏览器提交答案。
注意：答案是一个整数，不要提交任何多余的内容。
笨笨有话说：
哇塞！数据量真不少！看起来有很多相似的哦？情况并不太乐观呢？
不过试试看能不能排序？如果每个文件都排好序的话？情况会好很多哦？
歪歪有话说：
为什么排序呢？这么点数据让计算机处理起来倒也不算太吃力吧？
我发现需求似乎与我之前学过的集合概念有着相似之处。
#include <set>
#include <iostream>
#include <fstream>
using namespace std;
set<string> A;
set<string> B;
set<string> C;
int ans;
void read(set<string> &A,char *path) {
ifstream fin;
fin.open(path, ios_base::in);
while (!fin.eof()) {//eof==>end of file
string s;
fin >> s;
if(s.length()>0)
A.insert(s);
}
fin.close();
}
int main(int argc, const char *argv[]) {
read(A,"/Users/zhengwei/CLionProjects/lanqiao2018/2017_C_C/A.txt");
read(B,"/Users/zhengwei/CLionProjects/lanqiao2018/2017_C_C/B.txt");
read(C,"/Users/zhengwei/CLionProjects/lanqiao2018/2017_C_C/C.txt");
cout << A.size() << endl;
cout << B.size() << endl;
cout << C.size() << endl;
// 遍历集合A
set<string>::iterator iterA = A.begin();
while (iterA != A.end()) {
if (B.find(*iterA) != B.end() && C.find(*iterA) == C.end())//B中有但C中没有，计数+1
ans++;
iterA++;
}
cout << ans << endl;
return 0;
}03 算式 900 全排列
标题：算式900
小明的作业本上有道思考题：
看下面的算式：
(□□□□-□□□□)*□□=900
这些格子象征着从0到9的所有数字；这些十个格子恰好覆盖了从零到九的所有数字；特别提醒：任何以零开头的数字都应避免使用。
小明经过几天的努力，终于做出了答案！如下：
(5012-4987)*36=900
通过计算机搜索后,我们还发现了一个额外的解。本题的任务即为,请
您求得这个额外的解。
注意事项：
• 请确保提交时遵循示例中的格式要求。
• 运算符号及括号请使用英文字符输入。
• 算式中不允许出现任何空格字符。
注意：机器评卷，不要填写任何多余的内容，比如说明文字。
#include <iostream>
#include <algorithm> //next_permutation函数头文件
using namespace std;
int main(int argc, const char *argv[]) {
int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
do {
if (a[0] == 0 || a[4] == 0 || a[8] == 0)continue;
int x1 = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
int x2 = a[4] * 1000 + a[5] * 100 + a[6] * 10 + a[7];
int x3 = a[8] * 10 + a[9];
if ((x1 - x2) * x3 == 900) {
printf("(%d%d%d%d-%d%d%d%d)*%d%d=900\n",
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]);
}
} while (next_permutation(a, a + 10));
return 0;
}(5012-4987)*36=900
(6048-5973)*12=900
04 承压计算 二维数组的运用+计量的倍数扩大
标题：承压计算
X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的形状和大小完全一致。然而，在重量上则各有不同。
这些金属材料被整齐地堆成了金字塔形。
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X其中的数值代表金属块的质量（单位规模较大）。底层标记为X的位置对应着30台精密度极高的仪器设备。
在实验中，在每块原料均匀分布在下方两个金属块上时，在每个金属块上所承受的重量均为相等的比例；当所有金属块完全稳定后，在最底层放置了一个电子秤；由于该秤采用了非常精细的设计，在每一个测量周期内都能精准记录下每一个微小重量变化；由于该装置采用了独特的双层平衡结构设计，在每个测量周期内都能精准记录下每一个微小重量变化；该装置采用了独特的双层平衡结构设计
工作人员发现，其中读数最小的电子秤的示数为：2086458231
请你推算出：读数最大的电子秤的示数为多少？
注意：需要提交的是一个整数，不要填写任何多余的内容。
#include <iostream>
#include <algorithm>//sort函数头文件
using namespace std;
typedef long long LL;
LL arr[30][30];
int main(int argc, const char * argv[]) {
LL factor=1;
for (int i = 0; i < 30; ++i) {
factor<<=1;
}
// cout <<factor<<endl;
// 输入数据放入二维数组
for (int i = 0; i < 29; ++i) {
for (int j = 0; j <= i; ++j) {
LL a=0;
scanf("%lld",&a);
arr[i][j]=a*factor;
}
}
//自上而下处理a[i][j]*factor（2的30次方）-->除以2，计入a[i+1][j]和a[i+1][j+1]
//循环处理第1~N-1行
for (int i = 0; i < 29; ++i) {
for (int j = 0; j <=i ; ++j) {
LL ha =arr[i][j]/2;
arr[i+1][j]+=ha;
arr[i+1][j+1]+=ha;
}
}
//对a[N-1]这一行进行排序，查看最小值与factor之间的倍数关系，决定最大值是多少
sort(arr[29],arr[29]+30);
cout<<arr[29][0]/2<<","<<arr[29][29]/2<<endl;
return 0;
}2086458231,72665192664
05 杨辉三角 dp过程中，矩阵的压缩（一般从右到左）
标题： 杨辉三角
杨辉三角也叫帕斯卡三角，在很多数量关系中可以看到，十分重要。
第0行： 1
第1行： 1 1
第2行： 1 2 1
第3行： 1 3 3 1
第4行： 1 4 6 4 1
第5行： 1 5 10 10 5 1
1 6 15 20 15 6 1
两边的元素都是1， 中间的元素是左上角的元素与右上角的元素和。
我们约定，行号，列号都从0计数。
所以： 第6行的第2个元素是15，第3个元素是20
从直观上看，实际可能并不需要开辟一个二维数组；实际上一维数组也能够胜任。如下的程序灵活运用了一维数组的空间技巧来解决这个问题。
// 杨辉三角的第row行，第col列
long long f(int row, int col){
if(row<2) return 1;
if(col==0) return 1;
if(col==row) return 1;
long long a[1024];
a[0]=1;
a[1]=1;
int p = 2;
int q;
while(p<=row){
a[p] = 1;
for( _________________ ) a[q] = a[q] + a[q-1]; //填空
p++;
}
return a[col];
}
int main()
{
printf("%d\n", f(6,2));
printf("%d\n", f(6,3));
printf("%lld\n", f(40,20));
return 0;
}请深入研究源码文件，并修复划线处未完成的代码逻辑
#include <iostream>
using namespace std;
// 杨辉三角的第row行，第col列
long long f(int row, int col) {
if (row < 2) return 1;
if (col == 0) return 1;
if (col == row) return 1;
long long a[1024];
a[0] = 1;
a[1] = 1;
int p = 2;//临时的行号
int q;//列号
while (p <= row) {
a[p] = 1;
for (q = p - 1; q >= 1; q--)
a[q] = a[q] + a[q - 1]; //填空
p++;
}
return a[col];
}
int main() {
printf("%d\n", f(6, 2));
printf("%d\n", f(6, 3));
printf("%lld\n", f(40, 20));
return 0;
}06 最大公共子串 经典的dp问题
标题：最大公共子串
最大公共子串长度即为：求两个字符串的所有子串中能够相互匹配的部分的最大长度有多大。
例如，在字符串 a = "abcdkkk" 和 b = "baabcdadabc" 之间
此程序运用矩阵法实现求解，在处理小规模数据时仍具良好效果。
请分析该解法的思路，并补全划线部分缺失的代码。
#include <stdio.h>
#include <string.h>
#define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;
memset(a,0,sizeof(int)*N*N);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = __________________________; //填空
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
return 0;
}注意：仅需提供缺失的代码部分，并避免提供现有代码及相关符号；无需添加任何解释或说明内容
#include <stdio.h>
#include <string.h>
#define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;
memset(a,0,sizeof(int)*N*N);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = a[i-1][j-1]+1; //填空
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
int main()
{
printf("%d\n", f("abefecd", "becd"));
return 0;
}3
07 excel地址 变态了的进制问题
标题： Excel地址
Excel单元格的地址标记非常有趣,它通过字母来标识各列.例如,A代表第一列,B代表第二列,Z对应第26个字母,AA对应第27个字母,AB对应第二十八个位置,BA则对应第五十三个位置,...
通常来说，在Excel中最大列号会受到限制，因此转换起来并不会特别困难。
本题目即是要求对输入的数字, 输出其对应的Excel地址表示方式。
例如，
输入：
26
则程序应该输出：
Z
再例如，
输入：
2054
则程序应该输出：
BZZ
我们约定，输入的整数范围[1,2147483647]
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
注意：主函数应返回零；仅允许采用ANSI C/C++标准。禁止调用任何由编译环境或操作系统提供的特定功能。不允许在工程设置中省略标准库的包含声明。
提交程序时，注意选择所期望的语言类型和编译器类型。
笨笨有话说：
这有点像进制关系，又不完全是。好像末2位是以1当26，末3位是以1当26*26
歪歪有话说：
比起将字母序列转换为数字而言, 反过来则略显繁琐, 不过相比而言, 计算机处理速度非常迅速.
#include <string>
#include <iostream>
using namespace std;
int ans[100];
void solve1(long n) {
for (long i = 1; i <= n; ++i) {
ans[0]++;
int tmp = 0;
if (ans[0] == 27) {
tmp = 1;//表示进位
ans[0] = 1;//回到1
// 进位往后作用
int t = 1;//下标
while (tmp > 0 && t < 100) {
ans[t] += tmp;
if (ans[t] == 27) {
ans[t] = 1;
tmp = 1;
} else {
tmp = 0;
}
t++;
}
}
}
string s;
for (int k = 0; k < 100; ++k) {
if (ans[k] == 0)break;
s.insert(s.begin(), 'A' + (ans[k] - 1));
}
cout << s << endl;
}
int main(int argc, const char *argv[]) {
long n;
cin >> n;
solve1(n);
int cnt = 0;
while (n) {
if (n % 26 == 0) {
ans[cnt++] = 26;//特殊处理，能除尽的情况下，把26作为余数
n = n / 26 - 1;//商减少1，作为被除数
} else {
ans[cnt++] = n % 26;//把余数记录
n /= 26;//将商作为新的被除数
}
}
for (int i = cnt - 1; i >= 0; --i) {
cout << (char) ('A' + (ans[i] - 1));
}
return 0;
}08 九宫幻方 枚举比对
标题：九宫幻方
小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。
三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，
通过这样的一句口诀就能够非常完美的构造出一个九宫格来。4 9 2
3 5 7
8 1 6
有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。
现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉，交给邻居家的小朋友来进行还原，
并且希望她能够判断出究竟是不是只有一个解。
而你呢，也被小明交付了同样的任务，但是不同的是，你需要写一个程序~测试数据仅包含一组。
每组测试数据为一个...的矩阵，在给定任意一个完整的...时都能恢复出至少一组有效的解。
对于全部测试用例的数据集而言，在给定任意一个完整的...时都能恢复出至少一组有效的解。
如果仅当能够重建一个有效的三阶幻方阵，则完成该运算；否则输出“Too Many”（不包含引号）。
样例输入
0 7 2
0 5 0
0 3 0
样例输出
6 7 2
1 5 9
8 3 4
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
注意：
主函数必须返回零值;
仅允许采用ANSI C和ANSI C++标准;
禁止使用任何基于编译环境或操作系统的特定库函数;
所有所需的外部函数必须明确包含在源文件中;
工程配置不得跳过常用头文件的包含
提交程序时，注意选择所期望的语言类型和编译器类型。
笨笨有话说：
我也很喜欢这类题目。既然九宫幻方一共也不算太多数，我就不用太麻烦地一个个列出来好了。
也不能太随便呢？总得找个规律来。
#include <iostream>
/*
4 9 2
3 5 7
8 1 6*/
int all[8][9] = {{4, 9, 2, 3, 5, 7, 8, 1, 6},
{8, 1, 6, 3, 5, 7, 4, 9, 2},//上下
{2, 9, 4, 7, 5, 3, 6, 1, 8},//左右
{8, 3, 4, 1, 5, 9, 6, 7, 2},//右旋
{4, 3, 8, 9, 5, 1, 2, 7, 6},//右旋：左右
{6, 7, 2, 1, 5, 9, 8, 3, 4},//右旋：上下
{6, 1, 8, 7, 5, 3, 2, 9, 4},//再右旋
{2, 7, 6, 9, 5, 1, 4, 3, 8}}//再右旋之右旋
;
int test(int data[9]) {
int cnt = 0, ans = -1;
for (int i = 0; i < 8; ++i) {
bool ok = true;
for (int j = 0; j < 9; ++j) {
if (data[j] == 0)continue;
if (data[j] != all[i][j]) {
ok = false;
break;
}
}
if (ok) {
cnt++;
ans = i;
}
}
if (cnt == 1) {
return ans;
} else {
return -1;
}
}
int main(int argc, const char *argv[]) {
int data[9];
for (int i = 0; i < 9; ++i) {
scanf("%d", &data[i]);
}
int index = test(data);
if (index == -1) {
printf("Too Many\n");
} else {
printf("%d %d %d\n", all[index][0], all[index][1], all[index][2]);
printf("%d %d %d\n", all[index][3], all[index][4], all[index][5]);
printf("%d %d %d\n", all[index][6], all[index][7], all[index][8]);
}
return 0;
}09 拉马车 模拟+队列（string来完成了队列操作）queue，vector，string
标题：拉马车
在童年时期你是否接触过纸牌游戏？有一种被称为"拉马车"的游戏，在这种游戏中其规则简单明了且具有吸引力。
其游戏规则如下：
假设参与游戏的小朋友为A和B两人，在游戏开始时他们各自获得一组随机排列的纸牌。
具体而言：
A方拥有的纸牌序列为[K,… ,A]
而B方则拥有另一组不同的排列顺序[K,… ,4]
其中的X表示“10”，我们忽略了纸牌的花色。
从A方开始，A、B双方轮流出牌。
每当轮到某一方出牌时，在其纸牌堆顶端移除一张卡片，并将其置于桌面上方；如果手中还有其他纸牌，则将这张卡片放置在其顶端；若有剩余纸牌，则无需额外操作。
此例中，游戏过程：
A出K，B出2，A出8，B出7，A出X，此时桌上的序列为：
K,2,8,7,X
当B轮到出牌时，
其K若与桌面上纸牌序列中的K一致，
则将该K连同夹在其中的所有纸牌全部赢回，
并放入自己手中纸堆尾部。
此时，
双方手中纸堆依次为：
A方：[K,A,Q,J,K]
B方：[2,K,J,Q,K]
赢得比赛的一方继续进行出牌。具体来说就是B随后打出大王（K），接着是A打出黑桃皇后（K）。随后由B打出黑桃十点（J），接着再次赢得比赛的大王（A）。最后由双方各自打出小王（X）、小红和红桃皇后（J），从而再次赢得比赛的大王（K）。
注意：更多的时候赢牌的一方并不能把桌上的牌都赢走，而是拿走相同牌点及其中间的部分。
但无论如何，都是赢牌的一方继续出牌，有的时候刚一出牌又赢了，也是允许的。
当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。
对于本例的初始手牌情况下，最后A会输掉，而B最后的手里牌为：9K2A62KAX58K57KJ5
本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出-1。由两行组成的数据分别代表A和B双方最初持有的牌序列。
这些数据中的每个串都对应于一方玩家在游戏开始时手中的全部卡片。
系统将根据游戏规则自动计算出最终胜者，并将结果以一行的形式呈现。
这一行中的字符串详细列出了赢家手中剩余的所有卡片信息，
包括所有未被对方击败或抢夺的卡牌。
例如，
输入：
96J5A898QA
6278A7Q973
则程序应该输出：
2J9A7QA6Q6889977
再比如，
输入：
25663K6X7448
J88A5KJXX45A
则程序应该输出：
6KAJ458KXAX885XJ645
我们约定，输入的串的长度不超过30
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
需要注意的地方：
主函数应返回零值。
代码需严格遵循ANSI C和ANSI C++标准。
代码不得调用任何依赖于特定编译环境或操作系统功能的特殊函数。
所有所需的外部函数必须明确包含在源文件头部。
工程配置不得有意忽略常用头文件声明。
提交程序时，注意选择所期望的语言类型和编译器类型。
笨笨说些话：
在不断删减前端的同时还要补充末尾，
希望游戏结束前系统不会再使用到边缘附近的数组。
歪歪有话说：
反正串也不长，不如每次操作都返回一个新的串。
默默默有话说：
我一般不开口意见，在这种情况下表现得比较常见——通常我们会认为这种情况更适合动态数组而不是静态数组——我觉得这个方案确实不错；不妨自行尝试一下。
#include <iostream>
using namespace std;
string A, B, C;//A的牌，B的牌，桌上的牌
/** * * @param x 正在操作的玩家手中的牌
* @param z 桌面上的牌
* @return
*/
bool op(string &x, string &z) {
if (x.length() == 0)return false;
bool ans = true;
char front = x[0];
long i = z.find(front);
if (i != string::npos) {//桌上有相同的牌
// 将这张牌插入x的尾部，并且将桌上0~i之间的牌依次插入x的尾部
x.insert(x.end(), front);
for (int j = 0; j <= i; ++j) {
x.insert(x.end(), z[j]);
}
z.erase(0, i + 1);//从桌面上移除这些牌
}else{
// 将这张牌放在面上（下标为0）
z.insert(z.begin(),front);
ans=false;
}
x.erase(x.begin());
return ans;
}
int main(int argc, const char *argv[]) {
cin >> A >> B;
bool flagA = true;//A能出牌的标志
bool flagB = false;//B能出牌的标志
while (1) {
if (flagA) {
flagA = op(A, C);
if (A.length() == 0) {
cout << B << endl;
break;
}
flagB = !flagA;
}
if (flagB) {
flagB = op(B, C);
if (B.length() == 0) {
cout << A << endl;
break;
}
flagA = !flagB;
}
}
return 0;
}10 图形排版 递推预处理 + 枚举求min + 抽象及操作的封装
标题：图形排版
小明需要在一篇文档中加入 N 张图片，其中第 i 张图片的宽度是 Wi，高度是 Hi。假设纸张宽度设定为 M，则小明使用的文档编辑工具采用了以下方式对图片进行自动排版问题。
该工具会按照图片顺序，在宽度 M 以内，将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。
例如在 M=10 的纸张上依次打印 3x4, 2x2, 3x3 三张图片，则效果如下图所示，这一行高度为4。
(分割线以上为列标尺，分割线以下为排版区域；数字组成的矩形为第x张图片占用的版面)0123456789
111
111 333
11122333
11122333
如果当前行剩余宽度大于0，并且小于下一张图片，则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向上取整)，
然后放入当前行。例如再放入一张4x9的图片，由于剩余宽度是2，这张图片会被压缩到2x5，再被放入第一行的末尾。
此时该行高度为5： 0123456789
-----------------
111
111 333
11122333
11122333 如果当前行剩余宽度为0，该工具会从下一行开始继续对剩余的图片进行排版，直到所有图片都处理完毕。
此时所有行的总高度和就是这 N 张图片的排版高度。例如再放入11x1, 5x5, 3x4 的图片后，效果如下图所示，总高度为11：0123456789
44111 44
111 33344
1112233344
1112233344
5555555555
66666
66666777
66666777
66666777
66666777
现在由于排版高度过高，图片的先后顺序也不能改变，小明只好从 N 张图片中选择一张删除掉以降低总高度。
他希望剩余N-1张图片按原顺序的排版高度最低，你能求出最低高度是多少么？第一行由两个数值M和N构成，其中M代表打印介质的宽度而N代表图片总数。
随后共N行，在每一行中都包含了两个数值Wi和Hi（i=1,2,...,N），这些数值分别对应第i个图像的尺寸参数。具体来说，在第i个图像中宽度参数为Wi、高度参数为Hi，则该图像的实际尺寸即为Wi×Hi。
对于30%的数据，满足1<=N<=1000
对于100%的数据，满足1<=N<=100000，1<=M, Wi, Hi<=100
输出：
一个整数，表示在删除掉某一张图片之后，排版高度最少能是多少。
样例输入：
4 3
2 2
2 3
2 2
样例输出：
2
另一个示例，
样例输入：
2 10
4 4
4 3
1 3
4 5
2 1
2 3
5 4
5 3
1 5
2 4
样例输出：
17
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
请注意以下事项：
main函数应返回零值；
仅允许采用ANSI C及ANSI C++标准；
禁止使用任何基于编译环境或操作系统的特殊库函数；
相关所需函数需提前在其源文件中包含声明；
工程配置时不得忽略常用头文件的包含声明。
提交程序时，注意选择所期望的语言类型和编译器类型。
首先筛选出无需排列的图片，并按顺序对余下图片进行排版设计。随后依次检查每一张未被选用的图片，并将其余被选用的图片插入到适当位置。在这一过程中，预处理步骤与求解过程共同利用了一个'填满一行'的通用函数
#include <cmath>
#include <iostream>
using namespace std;
#define MAXN 100005
int M, N;
int f[MAXN];
struct pic {
int w, h;
} pics[MAXN];
struct line {
int w, h;//已经使用的宽度，当前的高度
line() { w = 0, h = 0; }
line(int _w, int _h) {
w = _w, h = _h;
}
line operator+(pic _p) {
if (w + _p.w > M) {//对图片进行压缩
_p.h = ceil(1.0 * _p.h * (M - w) / _p.w);
_p.w = M - w;
}
return line(w + _p.w, max(h, _p.h));
}
bool full() {
return w == M;
}
void clr() { w = h = 0; }
};
//在已有的line的基础上，从第k张图开始插入，最终能得到的整体高度
int push_till_full(line a, int k) {
for (; k <= N && !a.full(); ++k) {//在行未满的情况下，添加图片
a = a + pics[k];
}
return a.h + f[k];
}
int main(int argc, const char *argv[]) {
scanf("%d%d", &M, &N);
for (int i = 1; i <= N; ++i) {
scanf("%d%d", &pics[i].w, &pics[i].h);
}
for (int i = N; i >= 1; --i) {
f[i] = push_till_full(line(0, 0), i);//f[i]的含义，i 号图片及其后的图片另起一行插入得到的高度
}
line a;//一开始没有宽度和高度,要填充的行
int ans = 1e7;
int per = 0;//记录之前完整行累计的高度
for (int i = 1; i <= N; ++i) {
//不要第i张pic
int new_h = per + push_till_full(a, i + 1);//历史上完整行的高度是per，从i+1张图插入得出的整体高度由函数计算出
ans = min(ans, new_h);//用第i+1张图填入a这个line
a = a + pics[i];//将第i张图放入，作为下次迭代的line
if (a.full()) {//行已经填满，要重置line，并且结算一个整行的高度
per += a.h;
a.clr();//开启一个新行,空行
}
}
cout<<ans<<endl;
return 0;
}