这题这么水怎么还是蓝啊(恼
即使这么水我还是脑子抽风交了好几遍
其实很简单:
不妨设正确密码长度为 \(len\) ,根据题意,在试到正确密码前都要先把长度小于 \(len\) 的密码全部试一遍,则最优情况就是试长度为 \(len\) 的密码时一遍试对,最劣情况就是把长度为 \(len\) 的所有密码试到最后才试对。
这里提供一种类似桶排序的实现思路:
首先把每个长度的密码个数存起来:
for(int i=1;i<=n;i++)
cin>>ps[i];
cin>>ps[0];len=ps[0].size();
for(int i=1;i<=n;i++)
if(ps[0]!=ps[i])//这里除去正确密码,方便后续计算
wd[ps[i].size()]++;
然后处理答案的时候:
for(int i=1;i<len;i++)ans+=wd[i];//最小是试完所有小于len的
cout<<ans/k*(k+5)+ans%k+1<<' ';//记得+1
ans+=wd[len];//加上长度等于len且与正确密码不同的
cout<<ans/k*(k+5)+ans%k+1<<endl;
这样就完美杜绝了考虑最后一次尝试后不用等5秒的问题(