5.14 美团后端笔试 ak
emmm写了一个半小时就ak了
看错题耽误了很多时间(不然还能更快一点？
话说现在美团还有没有hc呀，孩子五月份才开始找实习感觉已经寄了
第一题，给一个数组求k使得闭区间[k-1,k+1]内的数最多
数组内的数取值范围很小<100，直接暴力
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m;
int a[maxn];
int main(){
map<int,int> mp;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]++;
}
int ans=0;
for(int i=1;i<=100;i++){
ans=max(ans,mp[i]+mp[i+1]+mp[i-1]);
}
cout<<ans<<endl;
}第二题，二位数组，有两种格子一种探索过的，一种没有探索过的，只能向右向下走，问从(1,1)到(n,m)最少要经历多少个没探索过的格子
看错题了，没注意到只能向下或向右，耽误了很多时间，索性写了个dij
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pii;
const int maxn=2e2+5;
int n,m;
char mp[maxn][maxn];
int dis[maxn*maxn];
int dx[]={-1,0};
int dy[]={0,-1};
vector<Pii> g[maxn*maxn];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<2;k++){
int xx=i+dx[k];
int yy=j+dy[k];
if(xx>0&&xx<=n&&yy>0&&yy<=m){
if(mp[i][j]=='o')g[(xx-1)*m+yy-1].push_back(make_pair((i-1)*m+j-1,0));
else g[(xx-1)*m+yy-1].push_back(make_pair((i-1)*m+j-1,1));
}
}
}
}
memset(dis,0x3f,sizeof dis);
priority_queue<Pii,vector<Pii>,greater<Pii>> q;
q.push(make_pair(0,0));
dis[0]=0;
while(q.size()){
auto t=q.top();
int u=t.second;
q.pop();
if(dis[t.second]>t.first)continue;
for(auto [v,w]:g[u]){
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(make_pair(dis[v],v));
}
}
}
cout<<dis[(n-1)*m+m-1]<<endl;
}第三题，给只有+-组成的字符串，能使+变-，-变+最多k次，问操作之后最长的只由+组成的子串，n<10000
暴力枚举起点然后贪心改掉之后前k个-号
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pii;
const int maxn=1e4+5;
int n,m;
char s[maxn];
int main(){
cin>>n>>m;
cin>>(s+1);
int ans=0;
for(int i=1;i<=n-m+1;i++){
int cnt=0,us=m;
for(int j=i;j<=n;j++){
if(s[j]=='-'&&us<=0)break;
else if(s[j]=='-')us--;
cnt++;
}
ans=max(ans,cnt);
}
cout<<ans<<endl;
}第四题，n个商品，有各自的售价，q次操作，三种操作，询问销量最大的商品，询问利润最大的商品，使某种商品销量增加x
直接上线段树，两个线段树分别维护即可
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pii;
const int maxn=1e5+5;
int n,q;
int a[maxn];
struct segtree{
struct node{
int l,r;
int val,num;
}tree[maxn<<2];
void pushup(int p){
if(tree[p<<1].val>=tree[p<<1|1].val){
tree[p].val=tree[p<<1].val;
tree[p].num=tree[p<<1].num;
}else{
tree[p].val=tree[p<<1|1].val;
tree[p].num=tree[p<<1|1].num;
}
}
void build(int l,int r,int p=1){
tree[p].l=l,tree[p].r=r;
if(l==r){
tree[p].val=0;
tree[p].num=l;
return ;
}
int mid=(tree[p].l+tree[p].r)>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
pushup(p);
}
void change(int lr,int k,int p=1){
if(tree[p].l==tree[p].r){
tree[p].val+=k;
return ;
}
int mid=(tree[p].l+tree[p].r)>>1;
if(lr<=mid)change(lr,k,p<<1);
else change(lr,k,p<<1|1);
pushup(p);
}
}t1,t2;
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
t1.build(1,n);
t2.build(1,n);
while(q--){
string opt;
cin>>opt;
if(opt=="Add"){
int x,y;
cin>>x>>y;
t1.change(x,y);
t2.change(x,y*a[x]);
}else{
string tp;
cin>>tp;
if(tp=="BestSales")cout<<t1.tree[1].num<<endl;
else cout<<t2.tree[1].num<<endl;
}
}
}第五题，n个商品有各自的售价，两个人一个人喜欢其中a种，另外一个人喜欢其中b种，询问最少花多少钱可以使买到的商品中有x个第一个人喜欢的，同时也有x个第二个人喜欢的（可以重叠）
贪心双指针，提取出三个数组，分别为只有a第一个人喜欢的商品va，只有第二个人喜欢的商品vb，两个人共同喜欢的商品vab，排序，然后两个指针ij，每次贪心选择min(va[i]+vb[i],vab[j])，然后相应的指针后移即可
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m;
int numa,numb,a[maxn],b[maxn],c[maxn];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>c[i];
map<int,int> mp;
cin>>numa;
for(int i=1;i<=numa;i++){
cin>>a[i];
mp[a[i]]++;
}
cin>>numb;
for(int i=1;i<=numb;i++){
cin>>b[i];
mp[b[i]]++;
}
if(numa<m||numb<m){
cout<<-1<<endl;
return 0;
}
vector<int> va,vb,vab;
for(int i=1;i<=numa;i++){
if(mp[a[i]]==1)va.push_back(c[a[i]]);
else vab.push_back(c[a[i]]);
}
for(int i=1;i<=numb;i++){
if(mp[b[i]]==1)vb.push_back(c[b[i]]);
}
sort(va.begin(),va.end());
sort(vb.begin(),vb.end());
sort(vab.begin(),vab.end());
int ans=0;
for(int cnt=1,i=0,j=0;cnt<=m;cnt++){
int tmp1=1e9;
int tmp2=1e9;
if(i<va.size()&&i<vb.size())tmp1=va[i]+vb[i];
if(j<vab.size())tmp2=vab[j];
if(tmp1<tmp2){
ans+=tmp1;
i++;
}else{
ans+=tmp2;
j++;
}
}
cout<<ans<<endl;
}#美团##题解#
海康威视公司福利 334人发布