阿里巴巴3.8技术岗笔试题
第一题
给你N个正整数，从小到大排序，然后问从第一个数字开始没出现的第k个正整数是多少。
T组 1<=T<=1000
1<=N<=1e5 1<=k<=1e8
比如
T组 1<=T<=1000
1<=N<=1e5 1<=k<=1e8
比如
1
5 2
3 4 6 7 9
第一个没出现的是5 第二个没出现是8
所以输出8
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；
给你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
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
