题解：UVA414 Machined Surfaces

UVA414 Machined Surfaces

题目大意

给出一个零件的左右两半，用 X 表示零件，用空格表示空隙。询问如果将左右两边拼合起来后空隙（即空格）的数目。

解题思路

考虑使用 $minn$ 记录两部分在每行上的最短间隔，即每行上空格的最少数目，并用 $tot$ 记录空格的总数。显然两个零件最多可以“相互靠近” $minn$ 格而不发生重叠。定义行数 $N$，则两部分拼合后空格的数目为 $tot - minn \times N$。

代码

#include <iostream>

#ifdef ONLINE_JUDGE
#    define getchar getchar_unlocked
#endif

using namespace std;

inline int read() {
    char c = getchar();
    int  x = 0, f = 1;
    for (; !isdigit(c); c = getchar())
        if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x * f;
}

#define r(a) (a) = read()

int    N;
int    ans, minn, now;
string s;

signed main() {
    while (1) {
        cin >> N;
        ans  = 0;
        minn = 100;
        cin.ignore();
        if (!N) break;
        for (int i = 1; i <= N; i++) {
            getline(cin, s);
            now = 0;
            for (auto c : s)
                if (c == ' ') now++;
            minn = min(minn, now);
            ans += now;
        }
        ans -= minn * N;
        printf("%d\n", ans);
    }
    return 0;
}