座位预定

https://ac.nowcoder.com/acm/contest/318/C

C++版本一

题解：

没有什么算法，也不怎么需要动脑，完完全全只考察了你们的代码编写和实现能力。写的时候尽量用几个函数将不同的情况进行分类讨论，混在一起写容易出现bug。只需要按题面描述的所有情况模拟就可以了。

#include <bits/stdc++.h>
using namespace std;

int r, n, _;
char mp[55][15];
int seat[55];
int sta[5][2] = {{5, 7}, {3, 9}, {1, 11}, {6, 6}, {2, 10}};

int cal_left() {
    int num = 0;
    for (int j = 1; j <= 5; j++) {
        for (int k = 1; k <= r + 3; k++)
            num += (mp[k][j] != '-' && mp[k][j] != '.');
    }
    return num;
}
int cal_right() {
    int num = 0;
    for (int j = 7; j <= 11; j++) {
        for (int k = 1; k <= r + 3; k++)
            num += (mp[k][j] != '-' && mp[k][j] != '.');
    }
    return num;
}
int get_min() {
    int id = 0, mn = 1e9, mx = 0;
    for (int j = 2; j < r + 3; j++) {
        if (seat[j] > mx) {
            mx = seat[j];
            id = j;
            mn = min(abs(j - 1), abs(j - (r / 2 + 2)));
            mn = min(mn, abs(j - (r + 3)));
        } else if (seat[j] == mx) {
            int cnt = min(abs(j - 1), abs(j - (r / 2 + 2)));
            cnt = min(abs(j - (r + 3)), cnt);
            if (mn > cnt) {
                id = j;
                mn = cnt;
            }
        }
    }
    return id;
}

void update(int row, char s) {
    for (int i = 0; i < 5; i++) {
        int p = sta[i][0], q = sta[i][1];
        if (mp[row][p] == '-' || mp[row][q] == '-') {
            if (mp[row][p] == '-' && mp[row][q] != '-')
                mp[row][p] = s;
            else if (mp[row][p] != '-' && mp[row][q] == '-')
                mp[row][q] = s;
            else {
                int num1 = cal_left(), num2 = cal_right();
                if (num1 <= num2)
                    mp[row][p] = s;
                else
                    mp[row][q] = s;
            }
            return;
        }
    }
}

int main() {
    int cas = 1;
    for (scanf("%d", &_); _; _--) {
        memset(seat, 0, sizeof(seat));
        memset(mp, 0, sizeof(mp));
        scanf("%d%d", &r, &n);
        int flag = 0;
        for (int i = 1; i <= r + 3; i ++) {
            scanf("%s", mp[i] + 1);
            for (int j = 1; j <= 11; j++) {
                if (mp[i][j] == '-')
                    seat[i]++;
            }
            if (i == 2 && seat[i] > 0)
                flag = 1;
            if (i == r / 2 + 3 && seat[i] > 0)
                flag = 1;
        }
        for (int i = 0; i < n; i++) {
            if (flag) {
                if (seat[2] >= seat[r / 2 + 3]) {
                    update(2, i + 'a');
                    seat[2]--;
                } else {
                    update(r / 2 + 3, i + 'a');
                    seat[r / 2 + 3]--;
                }
                if (seat[2] == 0 && seat[r / 2 + 3] == 0)
                    flag = 0;
            } else {
                int id = get_min();
                update(id, i + 'a');
                seat[id]--;
            }
        }
        printf("Case #%d:\n", cas++);
        for (int i = 1; i <= r + 3; i++)
            printf("%s\n", mp[i] + 1);
    }
    return 0;
}

C++版本二 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
 
using namespace std;
 
long long T, r, n, s[110][110], v[110][100], h[110], e[60], w[13], lef, rig;
char c[110][101];
 
inline void read(long long &x)
{
    int k = 1; x = 0;
    char c = getchar();
    while (!isdigit(c))
        if (c == '-') c = getchar(), k = -1;
        else c = getchar();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48),
        c = getchar();
    x *= k;
}
 
inline void Get(char &c)
{
    c = '\n';
    while (c == '\n') c = getchar();
}
 
inline int choosel()
{
    if (e[2] && e[(r >> 1) + 3])
    {
        if (e[2] == e[(r >> 1) + 3])
            { --e[2]; return 2; }
        if (e[2] > e[(r >> 1) + 3])
            { --e[2]; return 2; }
        --e[(r >> 1) + 3]; return (r >> 1) + 3;
    }
    if (e[2]) { --e[2]; return 2; }
    if (e[(r >> 1) + 3])
        { --e[(r >> 1) + 3]; return (r >> 1) + 3; }
    int now = 0, id;
    for (int i = 1; i <= r + 3; ++i)
        h[i] += e[i] * 1000000;
    for (int i = 1; i <= r + 3; ++i)
        if (h[i] > now && e[i] > 0)
            now = h[i], id = i;
    for (int i = 1; i <= r + 3; ++i)
        h[i] -= e[i] * 1000000;
    --e[id];
    return id;
}
 
inline int chooseh(int x)
{
    int now = 0, id = 0;
    if (lef <= rig)
        for (int j = 1; j <= 5; ++j)
            if (w[j]) w[j] += 1;
    if (lef > rig)
        for (int j = 7; j <= 11; ++j)
            if (w[j]) w[j] += 1;
    for (int i = 1; i <= 11; ++i)
        if (w[i] > now && v[x][i] == 0)
            now = w[i], id = i;
    if (lef <= rig)
        for (int j = 1; j <= 5; ++j)
            if (w[j]) w[j] -= 1;
    if (lef > rig)
        for (int j = 7; j <= 11; ++j)
            if (w[j]) w[j] -= 1;
    if (id <= 5) ++lef;
    if (id >= 7) ++rig;
    return id;
}
 
signed main()
{
    read(T);
    for (int plk = 1; plk <= T; ++plk)
    {
        memset(v, 0, sizeof(v));
        memset(h, 0, sizeof(h));
        fill(e + 1, e + 55, 11);
        lef = 0, rig = 0;
        int ex, ey;
        read(r), read(n);
        for (int i = 1; i <= r + 3; ++i)
            for (int j = 1; j <= 11; ++j)
            {
                Get(c[i][j]);
                v[i][j] = (c[i][j] == '#');
                if (v[i][j])
                {
                    --e[i];
                    if (j <= 5) ++lef;
                    if (j >= 7) ++rig;
                }
                if (c[i][j] == '.')
                    v[i][j] = 1,
                    --e[i];
            }
        h[1] = h[(r >> 1) + 2] = h[r + 3] = 600000;
        for (int l = 1; l <= r + 3; ++l)
            for (int i = 2; i <= r + 2; ++i)
                if (i != (r >> 1) + 2)
                    h[i] = max(h[i - 1], h[i + 1]) - 10000;
        for (int i = 1; i <= r + 3; ++i)
            h[i] += (n - i + 1) * 100;
        w[5] = w[7] = 1000000, w[3] = w[9] = 990000, w[1] = w[11] = 980000, w[2] = w[10] = 960000, w[6] = 970000;
        for (int k = 0; k < n; ++k)
        {
            ex = choosel();
            ey = chooseh(ex);
            c[ex][ey] = char(k + 'a');
            v[ex][ey] = 1;     
        }
        printf("Case #%d:\n", plk);
        for (int i = 1; i <= r + 3; ++i)
        {
            for (int j = 1; j <= 11; ++j)
                printf("%c", c[i][j]);
            puts("");
        }
 
    }
    return 0;
}