问题标题: 酷町堂：淡黄的长裙，蓬松的头发，我拉着你到这里来看1548

Question

0

已解决

王子健

初级天翼

1548 游戏之金币增长经验值：1200

题目描述 Description

小王是一个竞技游戏爱好者，在这一年中进行了N盘游戏，每盘游戏中获得的金币数是不同的，现在他想统计在这么多盘游戏中有多少次两盘游戏金币的差值等于C。例如进行5盘游戏，要求算有多少次两盘游戏差值等于20的情况（10 30 50 24 32），答案是2.

输入描述 Input Description

第一行包括2个非负整数N和C，中间用空格隔开。

第二行有N个整数，中间用空格隔开，作为要求处理的那串数。

输出描述 Output Description

输出一行，表示该串数中包含的所有满足A-B=C的数对的个数。

样例输入 Sample Input

4 1 1 1 2 3

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

对于73%的数据，N <= 2000；

对于100%的数据，N <= 200000。

N的测试数据太大了，我对桶排又不太熟悉，谁能叫我一下，20豆豆

酷町豆刷题求解 C++ 12条评论 4 年，6 月前

Answer 1

已采纳

李泽远

高级天翼

输入n和c，0到n-1的循环输入数组a，每次t[a[i]]++，用桶计数，

然后对a进行sort快排（数组a从0开始），

接着遍历a数组，a[i]表示当前的数，t[a[i]]表示这个数出现了几次，用cnt计数

for(int i=0;i<n;i++)

if(t[a[i]-c])//如果这个数减去c存在的话（也就是【两盘游戏金币的差值等于c】这个数组元素存在的话）

cnt+=t[a[i]-c];//这个数减去c的差出现了几次，计数

最后输出cnt。

PS：我觉得你的题目起的挺好，新颖有创意，还押韵，别理那些钢筋。

李泽远在2020-05-10 17:48:01追加了内容

结贴吧。

Answer 2

王子逸

新手天翼

用快排，这样好，可以AC 相信我，望采纳，谢谢

王子逸在2020-05-07 18:19:36追加了内容

头文件#include<algorithm>

sort(a,a+n);

Answer 3

郑金顺

中级光能

Answer 4

邓涵睿

中级天翼

快排，怎么样，有人问过这个问题，望采纳蟹蟹

Answer 5

沈峻宇

资深天翼

用快排写，桶排当然不对的啦！

Answer 6

董子墨

中级天翼

核心：

希望这能唤醒你对埃氏筛法及桶排的记忆

Answer 7

赵朗

高级光能

用一个循环，判断是否越界,如果****，则再判断这个数出现过没有，出现了就累加。

································↑自己想

赵朗在2020-04-30 23:02:54追加了内容

知道你很腻害

不要谦虚o(>﹏<)o

Answer 8

董宇昊

初级启示者

标题真猥琐！

Answer 9

吴庞茂旭

资深光能

你学过power这道题么？这道类似，但不完全一样，一个是加，一个是减，power里面的加为了避免两种情况，第一种是避免1+2=3,而2+1同样等于3（如果没避免的话就产生了两个胖子，这就多余了一个），第二种是避免3+2=5，而1+4同样等于5，所以b【tmp】一定要在最后等于0，tmp也要<=1000看他有没有越界。而这道题减肯定是要定义tmp=a【i】-a【j】的，当然还要考虑a[j]-a[i],然后tmp必须>=0,因为c是非负整数。

好啦，题目也差不多讲完了，接下来就是快乐的编程时光啦！（请以后不要起这样的名字，不然酷町侠（I now 他是谁）会以法律的名义制裁你的！）

你看就行了，通不通过随你。

Answer 10

陈喆鹏

资深光能

有人刚问

Answer 11

张天璨

新手天翼

标题真猥琐！

Answer 12

曹博扬

初级天翼

快排

有人刚问了呀？

Answer 13

丁海洋

中级守护

这是我回答的，网址：https://wenda.codingtang.com/questions/7814/点击进入

问题标题: 酷町堂：淡黄的长裙，蓬松的头发，我拉着你到这里来看1548

13 个回答: