微众银行 秋招 2023.09.03 编程题目与题解

1、切糖果

小美想要买糖果店的一根长长的糖果。糖果店顾客可以从中选取一个位置然后老板会在那切断,糖果前端到那个切断位置的糖果就会出售给这位顾客。这个糖果其实不同段有着不同的口味,小美希望她选出来的糖果中各个段有着不同的口味,在这基础上希望能选出尽可能长的糖果。小美想知道她能买到最长多长的糖果,请你帮帮她。

输入

第一行 1 个整数 n,表示糖果的长度。

第二行 n 个整数 a1,a2,,an,其中 ai 表示从糖果前端开始第 i 段的口味,每段均 1 为单位长度。

对于 100% 的数据,1n500001ai50000

输出

输出一行一个整数表示能买到的糖果的最长长度,且其中不包含相同口味。

样例

1
2
3
4
5
6
7
8
9
10
输入:
5
1 2 3 3 4

输出:
3

提示:
如果我们买长度为4的糖果,包含的口味为[1,2,3,3],存在了重复。
而长度为3时,包含的口味为[1,2,3],不存在重复。因此长度3为最长的不存在重复口味糖果长度。

解答

只需要按顺序查看一下有没有数已经被标记即可,被标记了就停下来,之后的都不要了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int vis[N];
int main(){
int r,n,x;
scanf("%d",&n);
for(r=0;r<n;r++){
scanf("%d",&x);
if(vis[x]) break;
vis[x]=1;
}
printf("%d\n",r);
}

2、酷

酷酷的小明准备和小伙伴们展示他捏出来的超酷的橡皮泥士兵。在展示之前,小明发现有些橡皮泥士兵大小十分相似甚至相同,这让小明感觉不是很酷,因为小明想要他的橡皮泥作品都有自己的风格,即使是大小也要有区别。小明的 n 个橡皮泥士兵的大小分别为 a1,a2,,an,小明可以通过给某个士兵加一单位橡皮泥来使得其大小增加一单位。小明想知道如果他想要让所有的橡皮泥士兵大小都不相同,至少需要一共加多少单位橡皮泥。

输入

第一行 1 个整数 n,表示小明的橡皮泥士兵数量。

第二行 n 个整数 a1,a2,,an,分别表示小明的橡皮泥士兵的大小。

对于 100% 的数据,1n500001ai100000

输出

输出一行一个整数表示总共至少加多少单位的橡皮泥。

样例

1
2
3
4
5
6
7
8
9
10
11
12
输入:
5
1 1 2 3 3

输出:
5

提示:
我们给一个大小为1的橡皮泥士兵增加4单位橡皮泥,大小变为5;
再给一个大小为3的橡皮泥士兵增加1单位橡皮泥,大小变为4。
此时橡皮泥士兵们的大小分别为1、2、3、4、5,没有两个橡皮泥士兵拥有相同大小了。
可以证明没有更优方案。

解答

首先对数组中的所有元素进行排序,假设现在已经满足 a1a2an

为了保证所有橡皮泥士兵的用料最小,我们将从小到大给每个士兵设定一个大小下限 mi,如果 mi>ai,那么士兵的重量就需要补到 mi。接下来是计算这个下界,一开始 m1=。对于 1i<n,如果 aimi,那么说明当前橡皮泥士兵大小已经足够,下一个至少为 ai+1,即 mi+1=ai+1;否则,需要为士兵补充 miai 的大小,并且下一个大小至少为 mi+1=mi+1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int a[N],n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
ll ans=0;
int need=0;
for(int i=1;i<=n;i++){
if(a[i]<need){
ans+=need-a[i];
++need;
}
else{
need=a[i]+1;
}
}
printf("%lld\n",ans);
}


3、平均值

小明有一个数组。他挑选了一个有理数 u/v,现在他想知道这个数组有多少个子区间的平均值恰好等于 u/v。数组的子区间即是数组中连续的一段区间,如数组 [4,2,6] 6 个子区间 [4],[2],[6],[4,2],[2,6],[4,2,6]

输入

第一行有三个整数 n,u,v(1n,v100000,1unv),代表数组的长度,小明选择的有理数的分子和分母。输入保证 u v 的最大公因数是 1,即 u/v 是最简分数。

第二行有 n 个绝对值不超过 1000000 的整数,代表数组中的元素。

数字间两两有空格隔开。

输出

输出一个非负整数,代表所求的答案。

样例

1
2
3
4
5
6
输入:
6 5 2
2 4 1 3 2 3

输出:
6

解答

这题的思路和美团 2023.08.26 那场笔试的第五题类似。只要令 bi=aiu/v,那么问题就转化成求有多少个子数组的数组和为 0。更具体地说,令 b 的前缀和为 si=j=1ibj,其中 s0=0,那么相当于寻找有多少对 (i,j) 满足 0i<jnsi=sj 即可。

然而,这次的 s 是一个有理数(而不是一个分数)。怎么简单处理呢?只需要将 bi 中的所有数都扩大 v 倍即可。一个数组的元素和为 0,那么它的所有元素之和的任意倍数也为 0

更具体的说,令 ci=vaiu,并且令 c 的前缀和为 si=j=1icj,其中 s0=0,那么只需要寻找有多少对 (i,j) 满足 si=sj 即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
ll a[N],s[N];
int main(){
int n,u,v;
scanf("%d %d %d",&n,&u,&v);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
a[i]=a[i]*v-u;
s[i]=s[i-1]+a[i];
}
map<ll,int>mp;
mp[0]=1;
ll ans=0;
for(int i=1;i<=n;i++){
ans+=mp[s[i]];
++mp[s[i]];
}
printf("%lld\n",ans);
}