UVA-1610 聚会游戏 题解答案代码 算法竞赛入门经典第二版

GitHub – jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

题目不难，但是场景有点多，需要注意细节。

首先将字符串排序，找到最中间的两个字符串。对这两个字符串找一个可以分割的字符串即可。

注意条件是：优先字符串长度最小，其次是字典序最小。

因此需要注意两个字符串什么时候开始不一样，不一样的字符中间是否能容下其它字符，后续是否还有字符等，具体场景可直接查看代码。

AC代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> ve;

void output()
{
for (auto ip = ve.begin(); ip != ve.end(); ++ip)
cout << *ip << endl;
}

string computed(int a)
{
string s;
int i, j;
for (i = 0; i < ve[a – 1].size(); ++i)
{
if (i >= ve[a].size())
break;
if (ve[a][i] == ve[a – 1][i])
s.push_back(ve[a][i]);
else if (ve[a][i] == ve[a – 1][i] + 1)
{
if (i == ve[a].size() – 1 && i == ve[a – 1].size() – 1)
{
return ve[a – 1];
}
if ((i != ve[a].size() – 1) && (i != ve[a – 1].size() – 1))
{
s.push_back(ve[a][i]);
return s;
}
if ((i == ve[a].size() – 1) && (i != ve[a – 1].size() – 1))
{
s.push_back(ve[a – 1][i]);
for (j = i + 1; j < ve[a – 1].size(); ++j)
{
if (ve[a – 1][j] == 'Z')
s.push_back(ve[a – 1][j]);
else
{
if (j == ve[a – 1].size() – 1)
s.push_back(ve[a – 1][j]);
else
s.push_back(ve[a – 1][j] + 1);
return s;
}
}
return s;
}
if ((i != ve[a].size() – 1) && (i == ve[a – 1].size() – 1))
{
return ve[a – 1];
}
}
else
{
if (i == ve[a].size() – 1 && i == ve[a – 1].size() – 1)
{
return ve[a – 1];
}
if (i != ve[a].size() – 1 && i != ve[a – 1].size() – 1)
{
s.push_back(ve[a – 1][i] + 1);
return s;
}
if (i == ve[a].size() – 1 && i != ve[a – 1].size() – 1)
{
s.push_back(ve[a – 1][i] + 1);
return s;
}
if (i != ve[a].size() – 1 && i == ve[a – 1].size() – 1)
{
s.push_back(ve[a – 1][i] + 1);
return s;
}
}
}
if (i < ve[a].size())
return ve[a – 1];
return s;
}

int main()
{
int n, i, j;
string s;
while (cin >> n && n > 0)
{
ve.clear();
for (i = 0; i < n; ++i)
{
cin >> s;
ve.push_back(s);
}
sort(ve.begin(), ve.end());
i = n / 2;
cout << computed(i) << endl;
// output();
}
}