阿里算法工程师笔试——2020.08.03

过题情况

第一题:100%
第二题:100%
说实话这场笔试题目比较简单,25minAK

第一题:n个朋友,每个人有金币x,有m个房子,每个房子有舒适度和价格,当前仅当这个人金币数大于房子价格时才能购买,每个人至多买一个房子,每个房子最多被一个人买,求最大舒适度

按舒适度从大到小排序,然后二分选择金币刚好>=价格的人进行购买,这里用multiset进行删除操作。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+200;
struct node{
int a,b;
}c[maxn];
bool cmp(node a, node b){
if(a.a==b.a)return a.b<b.b;
return a.a>b.a;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
multiset<int> st;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
st.insert(x);
}
for(int i=0;i<m;i++)
scanf("%d%d",&c[i].a,&c[i].b);
sort(c,c+m,cmp);
long long ans=0;
multiset<int>::iterator it;
for(int i=0;i<m;i++){
it=st.lower_bound(c[i].b);
if(it!=st.end()){
ans+=c[i].a;
st.erase(it);
}
}
printf("%lld\n",ans);
return 0;
}

第二题:给定一个a-f组成的字符串,对其进行删除,要求所有的a在c和e之前且所有的c在e之前,所有的b在d和f之前且所有的d在f之前,求删除后满足串的最大长度

这里可以先把串拆成只由ace和bdf组成的串,之后对这两个串做处理,小技巧,把bdf也换成ace,这样就对两个ace的串进行操作。
一个小dp,dp[i][j]代表枚举到i位置,之前最后是j字母的最大方案数,a是0,c是1,e是2。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+20;
int dp[maxn][3];
int ans;
void solve(string t){
if(t=="")return;
int len=t.length();
if(t[0]=='a')dp[0][0]=1;
else if(t[0]=='c')dp[0][1]=1;
else dp[0][2]=1;
int cnt=1;
for(int i=1;i<len;i++){
if(t[i]=='a')
dp[i][0]=dp[i-1][0]+1;
else if(t[i]=='c')
dp[i][1]=max(dp[i-1][0], dp[i-1][1])+1;
else
dp[i][2]=max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2]))+1;
for(int j=0;j<3;j++){
dp[i][j]=max(dp[i][j],dp[i-1][j]);
cnt=max(cnt,dp[i][j]);
}
}
ans+=cnt;
}
int main(){
string s;
cin>>s;
string s1="",s2="";
int len=s.length();
for(int i=0;i<len;i++){
if(s[i]=='a'||s[i]=='c'||s[i]=='e')
s1+=s[i];
else s2+=(s[i]-1);
}
solve(s1);
memset(dp,0,sizeof(dp));
solve(s2);
printf("%d\n",ans);
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

阿里算法工程师笔试——2020.08.03

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 阿里算法工程师笔试——2020.08.03
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏