1、切糖果
小美想要买糖果店的一根长长的糖果。糖果店顾客可以从中选取一个位置然后老板会在那切断，糖果前端到那个切断位置的糖果就会出售给这位顾客。这个糖果其实不同段有着不同的口味，小美希望她选出来的糖果中各个段有着不同的口味，在这基础上希望能选出尽可能长的糖果。小美想知道她能买到最长多长的糖果，请你帮帮她。
输入
第一行 个整数 ，表示糖果的长度。
第二行 个整数 ，其中 表示从糖果前端开始第 段的口味，每段均 为单位长度。
对于 100% 的数据，
输出
输出一行一个整数表示能买到的糖果的最长长度，且其中不包含相同口味。
样例
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、酷
酷酷的小明准备和小伙伴们展示他捏出来的超酷的橡皮泥士兵。在展示之前，小明发现有些橡皮泥士兵大小十分相似甚至相同，这让小明感觉不是很酷，因为小明想要他的橡皮泥作品都有自己的风格，即使是大小也要有区别。小明的 个橡皮泥士兵的大小分别为 ，小明可以通过给某个士兵加一单位橡皮泥来使得其大小增加一单位。小明想知道如果他想要让所有的橡皮泥士兵大小都不相同，至少需要一共加多少单位橡皮泥。
输入
第一行 个整数 ，表示小明的橡皮泥士兵数量。
第二行 个整数 ，分别表示小明的橡皮泥士兵的大小。
对于 100% 的数据，
输出
输出一行一个整数表示总共至少加多少单位的橡皮泥。
样例
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，没有两个橡皮泥士兵拥有相同大小了。
可以证明没有更优方案。
|
解答
首先对数组中的所有元素进行排序，假设现在已经满足 。
为了保证所有橡皮泥士兵的用料最小，我们将从小到大给每个士兵设定一个大小下限 ，如果 ，那么士兵的重量就需要补到 。接下来是计算这个下界，一开始 。对于 ，如果 ，那么说明当前橡皮泥士兵大小已经足够，下一个至少为 ，即 ；否则，需要为士兵补充 的大小，并且下一个大小至少为 。
代码
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、平均值
小明有一个数组。他挑选了一个有理数 ，现在他想知道这个数组有多少个子区间的平均值恰好等于 。数组的子区间即是数组中连续的一段区间，如数组 有 个子区间 。
输入
第一行有三个整数 ，代表数组的长度，小明选择的有理数的分子和分母。输入保证 和 的最大公因数是 ，即 是最简分数。
第二行有 个绝对值不超过 的整数，代表数组中的元素。
数字间两两有空格隔开。
输出
输出一个非负整数，代表所求的答案。
样例
1
2
3
4
5
6
| 输入：
6 5 2
2 4 1 3 2 3
输出：
6
|
解答
这题的思路和美团 2023.08.26 那场笔试的第五题类似。只要令 ，那么问题就转化成求有多少个子数组的数组和为 。更具体地说，令 的前缀和为 ，其中 ，那么相当于寻找有多少对 满足 即可。
然而，这次的 是一个有理数（而不是一个分数）。怎么简单处理呢？只需要将 中的所有数都扩大 倍即可。一个数组的元素和为 ，那么它的所有元素之和的任意倍数也为 。
更具体的说，令 ，并且令 的前缀和为 ，其中 ，那么只需要寻找有多少对 满足 即可。
代码
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);
}
|