万革始笔试第一题求指点
求问万革始笔试第一题的答案，暴力搜索正确率70%
大概描述是这样：
ID编号是一个K位的0/1字符串，定义两个ID间的距离是不一样的位的数目，例如 01000与10100距离是3.
现在已经有N个ID了，要找一个ID，使得它和已有ID间的最小距离最大，求字典序最小的ID
暴力搜索70%的方法如下，有什么别的思路么？求大佬指点~
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int distance(string s1, string s2)
{
int cnt = 0;
for (int i = 0; i < s1.size(); ++i)
{
if (s1[i] != s2[i])
cnt++;
}
return cnt;
}
int main()
{
int n, k;
cin >> n >> k;
vector<string> s;
for (int i = 0; i < n; ++i)
{
string x;
cin >> x;
s.push_back(x);
}
string res;
int best = 0;
for (int i = 0; i < pow(2,k); ++i)
{
string t;
for (int j = 0; j < k; ++j)
{
if (i >> j & 0x1)
{
t = '1' + t;
}
else
t = '0' + t;
}
int mini = INT_MAX;
for (int j = 0; j < n; ++j)
{
int r = distance(t, s[j]);
if ( r < mini )
{
mini = r;
}
if (r < best)
break;
}
if (mini > best)
{
best = mini;
res = t;
}
}
cout << res << endl;
return 0;
}#万革始##笔试题目#
美团公司氛围 2186人发布
查看9道真题和解析