8.23贝壳找房开发岗笔试（c++）
第一题，卡路里，排序后顺序减就行了
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n,s;
int main()
{
scanf("%d %d",&n,&s);
int c[n];
for(int i=0;i<n;i++)
scanf("%d",&c[i]);
sort(c,c+n);
int ans=0;
for(int i=0;i<n;i++)
{
if(s>=c[i])
{
s-=c[i];
ans++;
}
else
break;
}
printf("%d\n",ans);
}
第二题，让字符串出现k次的最小字符串长度 实际上就是问字符串的前x个和后x个完全一样，数据范围很小，直接暴力就行了
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,k;
char s[55];
int ans;
int main()
{
scanf("%d %d",&n,&k);
scanf("%s",s);
for(int i=1;i<=n-1;i++)
{
int flag=1;
for(int j=0;j<i;j++)
{
if(s[j]!=s[n-i+j])
{
flag=0;
break;
}
}
if(flag)
ans=i;
}
printf("%s",s);
for(int i=1;i<k;i++)
printf("%s",s+ans);
printf("\n");
}
第三题，买的最多的贝壳数量，实际上就是模拟那个过程就行了，注意一下，最后贝壳的总数量可能超过int上限，所以说中间部分变量需要使用long long
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int num[111];
int dp[11111];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %d",&x,&y);
long long num=m/y;
if(num>x)
{
ans+=x;
m-=(long long)y*x;
}
else
{
ans+=num;
m-=(long long)y*num;
}
}
cout<<ans<<endl;
}
第四题，背包的综合运用，第一步实际上是问一个容量为sum/2的背包最多能装多少东西，每个物品价值=体积
接下来第二步，对于sum分成的差值最小的两个部分，分别再做一次背包，这时候令每个物品的价值等于1，同时dp转移的时候判断一下状态是不是合法就行了
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n;
int num[111];
int dp[11111];
int sum,sum1,sum2;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&num[i]);
sum+=num[i];
}
sum1=sum/2;
for(int i=0;i<n;i++)
{
for(int j=sum1;j>=num[i];j--)
{
dp[j]=max(dp[j],dp[j-num[i]]+num[i]);
}
}
sum2=sum-dp[sum1];
printf("%d ",sum2-dp[sum1]);
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(int i=0;i<n;i++)
{
for(int j=sum2;j>=num[i];j--)
{
if(dp[j-num[i]]!=-1)
{
if(dp[j]==-1)
{
dp[j]=dp[j-num[i]]+1;
}
else
{
dp[j]=max(dp[j],dp[j-num[i]]+1);
}
}
}
}
int ans=abs(n-dp[sum2]-dp[sum2]);
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(int i=0;i<n;i++)
{
for(int j=sum-sum2;j>=num[i];j--)
{
if(dp[j-num[i]]!=-1)
{
if(dp[j]==-1)
{
dp[j]=dp[j-num[i]]+1;
}
else
{
dp[j]=max(dp[j],dp[j-num[i]]+1);
}
}
}
}
ans=max(ans,abs(n-dp[sum-sum2]-dp[sum-sum2]));
printf("%d\n",ans);
}
拼多多二面32人在聊
投递百度等公司10个岗位