【2018秋招笔试】2018.9.20 小米 测试工程师
前言
前段时间在做数学建模比赛,所以前几天也没时间帮对象做笔试题。
比赛刚告一段落,今天晚上就出现了两个笔试题,还冲突了。
对象做完一个才想起来小米的也是今晚笔试,好在还有四十分钟结束,于是继续转战小米的笔试题,飞快的昨晚单选题和多选题,只剩十分钟时间做编程题。
编程题有两道,打眼一看应该都能用搜索解决,第一题比较典型,很快解决AC,做第二题的时候还有一分钟,没搞定0%。
第一题
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10005;
bool flag=false;
int val[maxn],n,m;
int res[maxn],pos=0;//输出结果
void dfs(bool in,int step,int sum,int sur,int V)//in 表示是否用step个硬币,sur--剩余硬币价值和,V还需要多少价值才能填满
{
if(sur<V||sum>m||flag||step>n||m<val[step])return;//剪枝
if(sum==m)
{
//cout<<"YES"<<endl;
flag=true;
return;
}
if(in)
{
sum+=val[step];
res[pos]=step;
pos++;
dfs(true,step+1,sum,sur-val[step],V-val[step]);
pos--;
res[pos]=step;
pos++;
dfs(false,step+1,sum,sur-val[step],V-val[step]);
pos--;
sum-=val[step];
}
else
{
dfs(true,step+1,sum,sur,V);
dfs(false,step+1,sum,sur,V);
}
}
int main()
{
scanf("%d",&n);
int all=0;
for(int i=0;i<n;i++)
{
scanf("%d",&val[i]);
all+=val[i];
}
scanf("%d",&m);
sort(val,val+n);
dfs(true,0,0,all,m);
dfs(false,0,0,all,m);
if(!flag)cout<<"0";
else{
cout<<"1";
}
cout<<endl;
}
第二题
代码:
没时间做了……
原创声明
转载请注明:呓语 » 【2018秋招笔试】2018.9.20 小米 测试工程师