思路
只要回答是“是”,那么就会排除掉没有这个特征的动物,那么可行集就变少了,要想“是”的回答数量最多,则提问的次数就得越多,我们提问大部分动物有的特征,“不是”的可能会比较小,且可以刷“是”的次数。注意得到的结果要加 \(1\),因为最后不会只剩下一种动物,要再问一遍它们不同的特征才能得到答案。
代码
#include<iostream>
#include<string>
using namespace std;
struct animals{
string name,tz[114];
int k;
}a[114];
int main()
{
int n,maxn=-114514;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].name>>a[i].k;
for(int j=1;j<=a[i].k;j++) cin>>a[i].tz[j];
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
int t=0;
for(int k=1;k<=a[i].k;k++){
for(int l=1;l<=a[j].k;l++){
if(a[i].tz[k]==a[j].tz[l]){
t++;
break;
}
}
}
maxn=t>maxn?t:maxn;
}
}
cout<<maxn+1;
cout<<endl;
system("pause");
return 0;
}