2022 年 4 月 10 日拼多多笔试题解(AC3道)
2022年5月12日，已offer。
================================分割线===================================
这是第一次在牛客上些文章，有点不太习惯。我是昨天投递的拼多多，今天晚上参加的笔试。之前参加了一些大厂的面试，都没有收到很好的offer，孩子哭了。
因此写一波题目分析加上自己很low的代码攒一波幸运值吧，球球给孩子一个offer吧。
因为是孩子第一次在牛客上发文章，希望大家多多包容 ，也希望每个人都能够找到满意的OFFER，加油!
第一题
关于鹅卵石的颜色，还有颜色的等差数列之类的。
100%
#include <iostream>
#include <vector>
using namespace std;
//int a[100005];//鹅卵石
//100%
int m[100005][2];//
int main() {
int n;
cin>>n;
int tmp;
for(int i=1;i<=n;i++){
cin>>tmp;
if(m[tmp][0]==-1){
continue;
}
if(m[tmp][0]==0){
m[tmp][0]=i; //记录首个位置
}else{
//之前的记录正确
int d=i-m[tmp][0];
//第二次出现
if(m[tmp][1]==0){
m[tmp][0]=i;
m[tmp][1]=d;
//>=3次出现
}else if(m[tmp][1]==d){
m[tmp][0]=i;
}else if(m[tmp][1]!=d){
m[tmp][0]=-1;
}
}
}
int cnt=0;
for(int i=1;i<=100005;i++){
if(m[i][0]!=0&&m[i][0]!=-1){
cnt++;
}
}
cout<<cnt<<endl;
for(int i=1;i<=100005;i++){
if(m[i][0]!=0&&m[i][0]!=-1){
cout<<i<<" "<<m[i][1]<<endl;
}
}
return 0;
}
//5
//1 1 2 1 3 第二题
关于一道BFS的题目，因为这类题目我写的话，边界条件往往要找很久，不太擅长，就跳过去了没有做。 0%。
第三题
电影院排座问题，有一个注意点，需要是long long 类型，要么最后只通过80%。
100%
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//100%
//int a[100000005];
long long int arr[100005];
long long int M,N,q,L,R;
long long int index(long long int l,long long int r){
if(r<l){
return l;
}//终止查询
long long int mid=(l+r)/2;
if(arr[mid]==L){
return mid;
}else if(arr[mid]<L){
return index(mid+1,r);
}else {
//arr[mid]>L
return index(l,mid-1);
}
}
int main() {
cin>>N>>M;
long long int tmp;
for(long long int i=0;i<N;i++){
cin>>tmp;
arr[i]=tmp;
}
sort(arr,arr+N);//从小到大进行排序
cin>>q;
for(long long int i=0;i<q;i++){
cin>>L>>R;
bool flag=false;
//二分查找L,或者比L小的最大值
long long int li=index(0,N-1);
if(arr[li]==L){
for(long long int j=li+1;j<N&&arr[j-1]+1<=R;j++){
if(arr[j]-arr[j-1]>1){
flag=true;
cout<<arr[j-1]+1<<endl;
break;
}
}
if(flag==false){
cout<<-1<<endl;
}
}
else {
cout<<L<<endl;
}
}
return 0;
}
//5 10000000000
//3 5 999999997 7 999999998
//100
//999999999 10000000000
//3 7
//6 8
//3 3
//3 4 第四题
这是一道安排的问题，有些人说是动态规划，但是我是用贪心做的。核心在于代码中的tmax，最大的时间。 100%
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//100%
long long int m,n,x;
long long int ans;
long long int a[505];//到达时间
int main() {
//车，载重，时间
cin>>m>>n>>x;
long long int tmp;
for(long long int i=0;i<m;i++){
cin>>tmp;
a[i]=tmp;
}
sort(a,a+m);//排好序
if(m==0){
cout<<0<<endl;
return 0;
}
ans=a[m-1]+x;//最后一程
long long int tmax=a[m-1];//当前的最大时间
for(long long int i=m-1-n;i>=0;){
if(a[i]+2*x>tmax){
ans=ans+a[i]+2*x-tmax;
tmax=a[i];
i=i-n;
}
else{
tmax=tmax-2*x;
i=i-n;
}
// else{
// break;
// }
}
cout<<ans<<endl;
return 0;
}
//10 2 10
//10
//10
//10
//10
//10
//10
//10
//10
//40
//40 
