中级天翼
https://judge.codingtang.com/problem/1772/
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int n,c,cnt=0;
void ABC(){
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(abs(a[i]-a[j])==c){
cnt++;
}
}
}
}
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ABC();
cout<<cnt;
return 0;
}我的80分超时代码，求优化
初级启示者
速度优化建议
第①行
，建议使用cstdio（卡常..）
第③行数组长度定义成200000即可
第④行cnt是全局变量，默认值为0，不用赋值
第⒂行可以用scanf("%d %d",&n,&c)，速度更快
第⒘行可以用scanf("%d",&a[i])来输入，效率更高
最后输出cnt可以用printf("%d",cnt)，速度更快
如果还是超时请@我，我会帮你改思路
赵逸凡在2020-03-04 09:36:57追加了内容
注：由于是卡常，有时候可以优化，用万能头文件
赵逸凡在2020-03-04 09:37:18追加了内容
注：i,j可以定义成全局变量
赵逸凡在2020-03-04 10:00:55追加了内容
我有想法了，类似于楼上，但是并不相同，所以不算抄袭
第一种方法：
首先可以先排序sort，不要用优先队列（1是要头文件，2是时间慢，而且不易于查找元素，还不如用链表，链表也不如用数组），然后用dp来解，区间dp，f[i][j]表示从第i个数到第j个数和为c的x,y对数，目标f[1][n]，动态转移方程可以从f[i+1][j]或者f[i][j-1]推过来加特判，时间复杂度O(n)左右。
赵逸凡在2020-03-04 10:31:36追加了内容
第二种方法（不稳定）：
首先先sort一遍，然后再穷举，题目说是要求出满足和为c的对数，因为题目的数组长度太大，所以我们被迫放弃使用二维坐标的桶作法。
再看题目，没说都是正数，所以放弃剪枝作法。
所以只能在你的思路上，先sort一遍，从小到大，时间也趋于O(n^2)，枚举时，针对a[i]，可以从a[i+1]往a[n]枚举（跟你一样），找到a[j]满足a[j]-a[i]=c（省去了abs函数），就cnt++，自找到满足的j以后，就一直往后找，如果某个a[k]-a[i]>c就停止a[i]的循环，进行a[i+1]的寻找。这样不会漏掉元素，因为是从前往后的（和你的类似）。
赵逸凡在2020-03-04 10:35:41追加了内容
@楼上 谢谢你的提醒，是的，第一种解法不需要sort一遍了，直接dp，加上也没多大影响.但是你的算法时间是O(n*logn)，不是O(log2n)，因为按你的说法.push()时间是O(log n)，不过你的算法比他的是快，我的也是
@缪鲲鹏
赵逸凡在2020-03-04 11:17:25追加了内容
@缪鲲鹏 这样不算提到队列吗？您还说了然后，说明这是相关联的
中级天翼
最先提出思路或把我的代码改错并且全面的采纳！！！
新手光能
对于这种题来说, 穷举太慢了
若果你学过greater<int>(),然后用sort排序来降序,再用穷举就AC了(其实就是sort的降序)
还有一种就是用map来记录
也许还可以用高性能的dp
但是对于你的代码,可以尝试用sort修改, 但思路要刷新一下, 不能停在这里
缪鲲鹏在2020-03-03 22:00:43追加了内容
另外我想说, 为什么你们这一届的学生都喜欢用万能头....(doge)
