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); }
|