企业官网建设流程全解析

题目描述

题目描述了一个由字符X和空格组成的数字图像。图像总是有252525列，行数NNN可变。第111列始终是X，属于左侧表面；第252525列始终是X，属于右侧表面。每行中，左侧表面是从第111列开始连续的一段X，右侧表面是从第252525列开始向左连续的一段X，中间有零个或多个空格。将左表面和右表面水平向中间移动，直到某一行中左表面的最右侧X恰好位于右表面最左侧X的左侧相邻位置。移动过程中，表面保持刚性，只做水平平移。要求计算移动后所有行中剩余的空格总数（即“空隙”）。

输入格式

输入包含多组图像数据。每组数据格式如下：

• 第一行一个无符号整数NNN（0<N<130 < N < 130<N<13），表示图像的行数。
• 接下来NNN行，每行恰好252525个字符：一个或多个X，然后零个或多个空格，然后一个或多个X。
• 输入以单独一行的一个000作为结束标志。

输出格式

对于每组图像数据，输出一个整数，表示移动后剩余的空格总数。

样例

输入

4 XXXXBBBBBBBBBBBBBBBBXXXXX XXXBBBBBBBBBBBBBBBXXXXXXX XXXXXBBBBBBBBBBBBBBBBXXXX XXBBBBBBBBBBBBBBBBBXXXXXX 2 XXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXX 1 XXXXXXXXXBBBBBBBBBBBBBBXX 0

（注：样例中的B实际为空格字符）

输出

4 0 0

题目分析

本题的核心是计算将左表面和右表面水平相向移动至接触后，所有行中剩余的空格总数。

问题转化

每行由左表面的X、中间的空格、右表面的X组成。设第iii行的空格数为space[i]\textit{space}[i]space[i]。当两表面移动接触时，所有行的左表面和右表面会同时移动。移动的距离由某一行中中间空隙最小的行决定（因为该行最先接触）。设最小空格数为m=min⁡(space[1],space[2],…,space[N])m = \min(\textit{space}[1], \textit{space}[2], \ldots, \textit{space}[N])m=min(space[1],space[2],…,space[N])。移动后，原本有mmm个空格的行会变成000个空格（两表面刚好接触），而原本空格数大于mmm的行，剩余空格数为space[i]−m\textit{space}[i] - mspace[i]−m。

因此，移动后剩余的空格总数为：
total=∑i=1N(space[i]−m)=(∑i=1Nspace[i])−N×m \textit{total} = \sum_{i=1}^{N} (\textit{space}[i] - m) = \left( \sum_{i=1}^{N} \textit{space}[i] \right) - N \times mtotal=i=1∑N​(space[i]−m)=(i=1∑N​space[i])−N×m

实现步骤

1. 读取NNN，若N=0N = 0N=0则结束。
2. 读取NNN行字符串，每行长度固定为252525。
3. 统计每行中空格的个数，存入数组。
4. 找出空格数的最小值mmm。
5. 计算总和减去N×mN \times mN×m，输出结果。

边界情况

• 如果某行没有空格（即左右表面已经接触或重叠），则该行空格数为000。
• 如果所有行都没有空格，则m=0m = 0m=0，总空隙为000。
• 输入保证每行的格式为：X…（若干）空格…X…，不会出现其他情况。

复杂度分析

每组数据需要扫描NNN行，每行252525个字符，时间复杂度O(25N)O(25N)O(25N)，N<13N < 13N<13，完全可接受。

代码实现

// Machined Surfaces// UVa ID: 414// Verdict: Accepted// Submission Date: 2016-07-13// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);string line;intN;while(cin>>N,N){cin.ignore(1024,'\n');vector<int>spaces;for(inti=1;i<=N;i++){getline(cin,line);spaces.push_back(count(line.begin(),line.end(),' '));}intminimum=*min_element(spaces.begin(),spaces.end()),total=0;total=accumulate(spaces.begin(),spaces.end(),total)-minimum*spaces.size();cout<<total<<endl;}return0;}