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;
}