本文共 18085 字，大约阅读时间需要 60 分钟。

01 贪吃蛇长度 数数 -> 输入+字符判断+计数

标题：贪吃蛇长度

+-------------------------------------------------+|                                                 ||    H######                      ####            ||          #                      #  #            ||          #                      #  #            ||          #     ####             #  #            ||          #     #  #             #  #            ||          ######@###             #  #            ||                #       ####     #  #            ||                #       #  #     #  #            ||            ####@#######@###     #  #            ||            #   #       #        #  #            || T          #####       #        #  #   ##       || #                      #      ###  ### ##       || ################       #      #      ####       ||                #       #      #         #       ||   ##############       #######@##########       ||   #                         ###                 ||   ###########################                   |+-------------------------------------------------+

小明在爷爷的私人收藏馆里找到一台老式电脑。居然没有图形界面，只能用控制台编程。

经过小明的一阵摸索，神奇地设计出了控制台上的贪食蛇游戏。

如上图，是游戏时画面截图。其中，H表示蛇头，T表示蛇尾。#表示蛇的身体，@表示身体交叉重叠的地方。你能说出现在的贪吃蛇长度是多少吗？其实，只要数出#的数目算1，数出@的数目，算2，再加上头尾各算1就计算好了。人工数一下？太累眼睛了，聪明的你为什么不让计算机帮忙呢？本题的要求就是： 请填写上图中贪食蛇的长度是多少？注意：需要提交的是一个整数，不要添加任何多余内容（比如说明或注释）

#include 
   
    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的运用

标题：兴趣小组

为丰富同学们的业余文化生活，某高校学生会创办了3个兴趣小组

（以下称A组，B组，C组）。 每个小组的学生名单分别在【A.txt】,【B.txt】和【C.txt】中。 每个文件中存储的是学生的学号。

由于工作需要，我们现在想知道：

既参加了A组，又参加了B组，但是没有参加C组的同学一共有多少人？

请你统计该数字并通过浏览器提交答案。

注意：答案是一个整数，不要提交任何多余的内容。

---

笨笨有话说：

哇塞！数字好多啊！一眼望过去就能发现相同的，好像没什么指望。 不过，可以排序啊，要是每个文件都是有序的，那就好多了。

歪歪有话说：

排什么序啊，这么几行数字对计算机不是太轻松了吗？ 我看着需求怎么和中学学过的集合很像啊…

#include 
   
    #include 
    
     #include 
     
      using namespace std;set
      
        A;set
       
         B;set
        
          C;int ans;void read(set
         
           &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
          
           ::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的数字，这10个方块刚好包含了0~9中的所有数字。

注意：0不能作为某个数字的首位。

小明经过几天的努力，终于做出了答案！如下：

(5012-4987)*36=900

用计算机搜索后，发现还有另外一个解，本题的任务就是：请你算出这另外的一个解。

注意：提交的格式需要与示例严格一致；

括号及运算符号不要用中文输入法； 整个算式中不能包含空格。

注意：机器评卷，不要填写任何多余的内容，比如说明文字。

#include 
   
    #include 
    
      //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 1X 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 
   
    #include 
    
     //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 <
     
      <
      
       除以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<
      
     
    
   

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 
   
    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问题

标题：最大公共子串

最大公共子串长度问题就是：

求两个串的所有子串中能够匹配上的最大长度是多少。

比如：“abcdkkk” 和 “baabcdadabc”，

可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。

请分析该解法的思路，并补全划线部分缺失的代码。

#include 
   
    #include 
    
     #define N 256int 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 
   
    #include 
    
     #define N 256int 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表示第1列， B表示第2列， Z表示第26列， AA表示第27列， AB表示第28列， BA表示第53列， …

当然Excel的最大列号是有限度的，所以转换起来不难。

如果我们想把这种表示法一般化，可以把很大的数字转换为很长的字母序列呢？

本题目即是要求对输入的数字, 输出其对应的Excel地址表示方式。

例如，

输入： 26 则程序应该输出： Z

再例如，

输入： 2054 则程序应该输出： BZZ

我们约定，输入的整数范围[1,2147483647]

资源约定：

峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：

main函数需要返回0; 只使用ANSI C/ANSI C++ 标准; 不要调用依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源文件中 #include 不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

---

笨笨有话说：

这有点像进制关系，又不完全是。好像末2位是以1当26，末3位是以1当26*26

歪歪有话说：

要是从字母序列转数字还好点，倒过来有点麻烦，不过计算机跑得快啊。

#include 
   
    #include 
    
     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

有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一个解。而你呢，也被小明交付了同样的任务，但是不同的是，你需要写一个程序~

输入格式：

输入仅包含单组测试数据。 每组测试数据为一个3*3的矩阵，其中为0的部分表示被小明抹去的部分。 对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。

输出格式：

如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）。

样例输入

0 7 2 0 5 0 0 3 0

样例输出

6 7 2 1 5 9 8 3 4

资源约定：

峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：

main函数需要返回0; 只使用ANSI C/ANSI C++ 标准; 不要调用依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源文件中 #include 不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

---

笨笨有话说：

我最喜欢这类题目了。既然九宫幻方一共也没有多少，我就不辞辛劳地一个一个写出来好了。 也不能太过分，好歹用个数组。

#include 
   
    /*4 9 23 5 78 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, 8, X, K, A, 2, A, 9, 5, A] B方：[2, 7, K, 5, J, 5, Q, 6, 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在内的以及两个K之间的纸牌都赢回来，放入自己牌的队尾。

注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。 此时，A、B双方的手里牌为： A方：[K, A, 2, A, 9, 5, A] B方：[5, J, 5, Q, 6, K, 4, K, X, 7, 8, 2, K]

赢牌的一方继续出牌。也就是B接着出5，A出K，B出J，A出A，B出5，又赢牌了。

5,K,J,A,5 此时双方手里牌： A方：[2, A, 9, 5, A] B方：[Q, 6, K, 4, K, X, 7, 8, 2, K, 5, A, J, K, 5]

注意：更多的时候赢牌的一方并不能把桌上的牌都赢走，而是拿走相同牌点及其中间的部分。但无论如何，都是赢牌的一方继续出牌，有的时候刚一出牌又赢了，也是允许的。当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。对于本例的初始手牌情况下，最后A会输掉，而B最后的手里牌为：

9K2A62KAX58K57KJ5

本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出-1。

输入为2行，2个串，分别表示A、B双方初始手里的牌序列。

输出为1行，1个串，表示A先出牌，最后赢的一方手里的牌序。

例如，

输入： 96J5A898QA 6278A7Q973

则程序应该输出：

2J9A7QA6Q6889977

再比如，

输入： 25663K6X7448 J88A5KJXX45A

则程序应该输出：

6KAJ458KXAX885XJ645

我们约定，输入的串的长度不超过30

资源约定：

峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：

main函数需要返回0; 只使用ANSI C/ANSI C++ 标准; 不要调用依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源文件中 #include 不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

---

笨笨有话说：

不断删除前边的，又要后边添加… 如果用数组，需要开一个大点的，请佛祖保佑在游戏结束前，不会用到数组的边缘。

歪歪有话说：

反正串也不长，不如每次操作都返回一个新的串。

默默有话说：

我一般都不吱声，这是典型的队列结构，动态数组最好，没有？自己造一个呗！

#include 
   
    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，小明使用的文档编辑工具会用以下方式对图片进行自动排版：

1. 该工具会按照图片顺序，在宽度 M 以内，将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。例如在 M=10 的纸张上依次打印 3x4, 2x2, 3x3 三张图片，则效果如下图所示，这一行高度为4。(分割线以上为列标尺，分割线以下为排版区域；数字组成的矩形为第x张图片占用的版面)

0123456789

111

111 333 11122333 11122333

2. 如果当前行剩余宽度大于0，并且小于下一张图片，则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向上取整)，然后放入当前行。例如再放入一张4x9的图片，由于剩余宽度是2，这张图片会被压缩到2x5，再被放入第一行的末尾。此时该行高度为5：

0123456789-----------------111     111  3331112233311122333

3. 如果当前行剩余宽度为0，该工具会从下一行开始继续对剩余的图片进行排版，直到所有图片都处理完毕。此时所有行的总高度和就是这 N 张图片的排版高度。例如再放入11x1, 5x5, 3x4 的图片后，效果如下图所示，总高度为11：

0123456789

44

111 44

111 33344 1112233344 1112233344 5555555555 66666 66666777 66666777 66666777 66666777

现在由于排版高度过高，图片的先后顺序也不能改变，小明只好从 N 张图片中选择一张删除掉以降低总高度。他希望剩余N-1张图片按原顺序的排版高度最低，你能求出最低高度是多少么？

输入：

第一行包含两个整数 M 和 N，分别表示纸张宽度和图片的数量。 接下来 N 行，每行2个整数Wi, Hi，表示第 i 个图大小为 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函数需要返回0; 只使用ANSI C/ANSI C++ 标准; 不要调用依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源文件中 #include 不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

//思路1：枚举不需要的图片，剩余的图片按次序排版，维护最低高度

//优化思路：可以倒序预处理出一个数组 f ，f(i) 表示 i 号图片及其后的图片另起一行插入得到的高度。 // 然后按顺序枚举哪一张图片不选，同时将选的图片插入。预处理和求解可以共用一个“放满一行”的函数

#include 
   
    #include 
    
     using namespace std;#define MAXN 100005int 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<
     
      <
     
    
   

转载地址：https://blog.csdn.net/ZYJ_OvO/article/details/115057109 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！