追梦算法----A-B数对
Description
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
好吧，题目是这样的：给出一串数以及一个数字 C，要求计算出所有 A - B = C的数对的个数（不同位置的数字一样的数对算不同的数对）。
Input
输入共两行。
第一行，两个整数 N, C。
第二行，N 个整数，作为要求处理的那串数。
Output
一行，表示该串数中包含的满足 A - B = C 的数对的个数。
Samples
输入数据 1
4 1
1 1 2 3
输出数据 1
3
Limitation
1s, 1024KiB for each test case.
这是一道二分算法模板题
反思总结：
1、首先这道题我们的思维转变很重要，求 c = a - b 我们可以将它们转变成 a = c + b 然后写一个函数在所给的数据中二分查找一遍。
2、因为使用的是二分查找，所以读完数据后，我们要对数据进行排序。
3、由于题目所给的符合 a 的数值，可能有多个（如： a （2）= c ( 1 ) + b ( 1 ) t题目所给的2 可能有多个），所以我们求得是一个区间范围
4、所以我们求第一个大于 a - 1 的数为 左边界（ l ）求一个第一个大于 a 的值为右边界（ r ），右边界 - 左边界 = 区间的值 ，把每一次的区间值累加即可得到答案。
做题的时候思路很乱，所以心态要稳住，思路要清晰，在思路乱的情况下重新思考，把做题思路一条一条的写下来。
#include
#include
#include
#include
#include
#include
#include
#include #include
#include
#include
#include
#include
using namespace std;
const int N=1e8+7;
int n,c,a[N],ans=0;
int find(int b) {int l=0,r=n;while(l>1;if(a[mid]>n>>c;for(int i=0; i>a[i];}sort(a,a+n);for(int i=0; i
方法二：
这道题的实质是求相同数字的个数。
可以使用一个数组将 b + c = a 对应的 b 的数量记录下来
由于 c 是固定的，所以读入 b 的时候将 vis 数组上 a 位置上的值进行累加
再将读入数据的数值循环一边，ans += vis 数组中读入数据位置上的值。
如：
4 1
1 1 2 3
1 -- > vis [ 2 ] , 1 -- > vis [ 2 ] , 2 -- > vis [ 3 ] , 3 -- > vis [ 4 ] ,
vis [ ] ={ 0 , 0 , 0 , 2 , 1 , 4 }。
注意：
题目没有给出数据范围，所以 vis 数组使用动态的 map 会比较好
#include
#include
#include
#include
#include
#include
#include
#include 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！