首页 > 阿里巴巴3.8技术岗笔试题
头像
精神病科黄主任
编辑于 2021-03-23 22:42
+ 关注

阿里巴巴3.8技术岗笔试题

第一题
给你N个正整数,从小到大排序,然后问从第一个数字开始没出现的第k个正整数是多少。
T组  1<=T<=1000
1<=N<=1e5    1<=k<=1e8
比如
1
5 2
3 4 6 7 9
第一个没出现的是5  第二个没出现是8
所以输出8

AC代码:
/*
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-08 18:49:21
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e6+50;
ll a[N],b[N];
int main(){
    int T;cin>>T;
    while(T--){
        int n,k;cin>>n>>k;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<n;i++){
            b[i]=a[i+1]-a[i]-1;
        }
        int flag=0;
        for(int i=1;i<n;i++){
            if(k>b[i]) k-=b[i];
            else{ 
                cout<<k+a[i]<<endl;
                flag=1;
                break;
            }
        }
        if(flag==0) cout<<a[n]+k<<endl;
    }
    return 0;
}



第二题
给你n个工人和m个任务,还有一个利润p,每个任务需要用到x[i]个工人,利润为y[i],问你分配工人后,有多少种方案数可以让利润不小于p,答案取模1e9+7;

T组  1<=T<=100
1<=n<=100
1<=m<=100
1<=x[i]<=100
1<=y[i]<=100

第一行输入T
接下来每组输入m n p
然后输入x[i]
接下来一行输入y[i]
样例
输入:
1
2 5 3
2 2
2 3

输出:
2

一种是只做第二个任务,利润为3,一种是两个任务都做,利润为5

他这题应该所有n总和有个限制,但是题目没说,不然我dp复杂度是1e8了都
要么就是数据弱了。

AC代码:
/*
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-08 18:53:38
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e2+50;
ll dp[N*N][N];   //dp[i][j]获得利益等于i,工人用了j个的方案数
int x[N],y[N];
int main(){
    ios::sync_with_stdio(0);
    int T;cin>>T;
    while(T--){
        int n,m,p;cin>>m>>n>>p;
        dp[0][0]=1;
        int S=0;
        for(int i=1;i<=m;i++){
            cin>>x[i];
        }
        for(int i=1;i<=m;i++){
            cin>>y[i];
            S+=y[i];
        }
        for(int i=1;i<=m;i++){
            for(int j=S;j>=y[i];j--){
                for(int k=n;k>=x[i];k--){
                    dp[j][k] += dp[j-y[i]][k-x[i]];
                    dp[j][k]%=mod;
                }
            }
        }
        ll ans=0;
        for(int i=p;i<=S;i++){
            for(int j=1;j<=n;j++) {
                ans+=dp[i][j];
                ans%=mod;
            }
        }
        for(int i=1;i<=S;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=0;
            }
        }
        cout<<ans%mod<<"\n";
    }
    return 0;
}

update:
第二题应该是数据水了
听NB群友说,我们可以注意到p<=100,所以已经大于100的利润我们可以看成一个整体去计算即可,而不需要逐一枚举。
所以复杂度是T * n * m *100 =1e8





全部评论

(7) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐