保山市住房和建设局网站,网站建设中 切片指什么,学校网站用途,建设网站美海房地产题目描述 小明一共有n块锻造石#xff0c;第块锻造石的属性值为ai. 现在小明决定从这n块锻造石中任取两块来锻造兵器 通过周密计算#xff0c;小明得出#xff0c;只有当两块锻造石的属性值的差值等于C#xff0c;兵器才能锻造成功 请你帮小明算算#xff0c;他有多少种选…题目描述 小明一共有n块锻造石第块锻造石的属性值为ai. 现在小明决定从这n块锻造石中任取两块来锻造兵器 通过周密计算小明得出只有当两块锻造石的属性值的差值等于C兵器才能锻造成功 请你帮小明算算他有多少种选取锻造石的方案可以使得锻造成功 输入描述 第一行包含两个整数nC其含义如题所述 接下来一行包含n个整数分别表示a1a2··an. 1 N 2 x 10^5|ai| 10^40 C 10^9 输出描述 输出共一行包含一个整数表示答案. 输入输出样例 6 3 8 4 5 7 7 4 5 解题思路
这个题是一道典型的双指针题要控制快指针和慢指针所对应的数据之差为C。
首先使用排序方法对输入数据进行排序是必要的。
然后快指针优先移动直到快慢指针数据之差至少为C接下来慢指针进行移动如果不是C就一定比C大就往后移动直到快慢指针之差至多为C。
到此就是一组快慢指针的移动此时可以判断快慢指针数据之差是否为C如果是就对ans做更新。这题的关键是ans更新多少我们思考后不难发现按照题目提供的例子两个7的石头可以与两个4的石头分别组成一组这意味着组合数量是满足要求的两个数值的石头的个数乘积那么我们只需要对快慢指针分别派生出一个新指针分别向后步进进行计数即可。
下面给出代码
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {Scanner sc new Scanner(System.in);BufferedReader in new BufferedReader(new InputStreamReader(System.in));String[] temp in.readLine().split( );int n Integer.parseInt(temp[0]);int c Integer.parseInt(temp[1]);temp in.readLine().split( );int[] data new int[n];for (int i 0; i n; i) {data[i] Integer.parseInt(temp[i]);}Arrays.sort(data);int slow 0, fast 0;long ans 0;while (fast n) {while (fast n data[fast] - data[slow] c) {fast;}while (fast n data[fast] - data[slow] c) {slow;}if (fast n data[fast] - data[slow] c) {int oldFast fast, oldSlow slow;while (fast n data[fast] data[oldFast]) {fast;}while (slow n data[slow] data[oldSlow]) {slow;}ans (long) (fast - oldFast) * (slow - oldSlow);}}System.out.println(ans);}
}
