P1102 A-B 数对
题目描述
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
好吧，题目是这样的：给出一串数以及一个数字 CC，要求计算出所有 A - B = CA?B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个整数 N, CN,C。
第二行，NN 个整数，作为要求处理的那串数。
输出格式
一行，表示该串数中包含的满足 A - B = CA?B=C 的数对的个数。
输入输出样例
输入 #1 复制
4 1
1 1 2 3
输出 #1 复制
3
说明/提示
对于 75%75% 的数据，1 \leq N \leq 20001≤N≤2000。
对于 100%100% 的数据，1 \leq N \leq 2 \times 10^51≤N≤2×10
5
。
保证所有输入数据都在 3232 位带符号整数范围内。
新添数据两组
思路：
这道题新添的数据好麻烦有点难过，先试用数组
我们要用sort来给那堆数排序
然后让一个个数进入数组
这个时候第一个参数就是记录看到底有多少个重复一样的用p表示
p表示的不是当前跟自己重复的是多少个，比如题目给的序列是1 1 2 3，那么看到2的时候p记录的是前面 1 有2个重复
这个时候判断2-1=1，那么答案就加2，(那么s=s+p)
如果是1 1 1 2 3，那么循环到第四个数字2的时候，答案就加3
如果是1 1 1 2 2 3，循环到第四个答案加3，循环到第五个数字，发现它和前面一样，也加3,因为有两个2一个和前面三个组成一组答案
然后，我们需要一个新的队列，如果当前数字和前一个一样，那么我们就每一个都加入队列
知道遇到跟前一个不一样的，比如 1 1 1 2 3，这个时候遇到2，队列里面有三个数字 1 1 1
那么只要这个队列不为空，就从队列头看起，如果 2 - 队列头 = 1那就 p++
比如 1 1 1 4 5 5 6
循环到4，发现队列头小于3
那么把队列头一个一个弹出(但是我们用的不是队列，这就用第一个while循环的作用，去除前面队列头太小的时候进行清除之前一样的数字)
弹出的时候p没有加加，然后队列就弹完了
之前那个如果是1的p加加之后还是要继续弹出队头
然后 2也得进队
也就是说我们的总体思想是，每一个元素都进队
但是如果你和前面的元素一样，就不需要执行什么判断了
如果你和前面的元素不一样，这个时候就要执行判断，看看排在你前面的队头有多少个跟你相差1
前面比你小的刚好1的判断完就全部弹出去了
或者如果前面全部没有刚好是1，那就弹到你之前没有数字
相当于队尾进一个数字，就看看要不要把前面的人推出去
这种思想去找答案
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int m,n,a[2000020],zi[2000020],c;
long long s=0;
int main()
{
scanf("%d%d",&n,&c);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n);zi[0]=a[1];int reat =1,front=0;long long p=0 ;for(int i=2;i<=n;i++){
if(a[i]==a[i-1]){
//找到相同的数字放入数组s=s+p;//如果前面有相同的数字满足条件，就需要把前面的情况相加//比如前面有三个1,之后又两个2满足条件就有6种，每个2三种zi[reat]=a[i];reat++;}else{
while(front<reat&&zi[front]<a[i]-c){
//如果前面数组头的过小//直接跳过front++;}p=0;while(front<reat&&zi[front]==a[i]-c){
//满足条件p++;// s=s+p;front++;}//下一个数，跟前面数组头不相同的数字zi[reat]=a[i];reat++;s=s+p;}}cout<<s;return 0;
}