题目描述:
参考博客
题意：
给两个大小为 n 的数组A， B， 判断数组中有多少对 满足 Ai + Aj > Bi + Bj。
解题思路：
由于 n 的大小限制，两个for循环必然超时。
调整不等式 为 (Ai - Bi) + (Aj - Bj) > 0 ，那么此时就可将两个数组转换为一个数组
然后从小到大排序，小的 + 大的如果 大于0即可
举例：
5
4 8 2 6 2
4 5 4 1 3
数组A - 数组B得到新的数组： 0 3 -2 5 -1
排序后： -2 -1 0 3 5
设置两个指针分别从左和从右往中间压缩， -2 + 5 > 0 那么表示5 加上从 -2 到 5 的任意数都满足 那么会出现 5 - 1 = 4 对
右指针往左走1 ， -2 + 3 > 0 同理， 4 - 1 = 3对 ， 答案为7
解题思路：
这道题这种解法很巧妙转换成一个数组，然后排序分别计算符合条件的。但是在提交的时候，遇到很多问题，我是用java写的，首先是需要用到快速输入输出，不然会超时，然后是在声明数组的时候，用int[] 声明也会超时，需要用Integer[] 。印象中，Integer是对象，用这种可能会造成内存的浪费，但是这样计算的速度却比int快，反正这道题挺迷的。
import java.io.*;import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String[] args) throws IOException {PrintWriter out = new PrintWriter(System.out);Reader scan = new Reader();int n=scan.nextInt();int[] arr=new int[n];for (int i = 0; i < n; i++) {arr[i]=scan.nextInt();}for (int i = 0; i < n; i++) {arr[i]-=scan.nextInt();}Arrays.sort(arr);long sum=0;int i=0;int j=n-1;while (i<j){if(arr[i]+arr[j]>0){sum+=(long) j-i;j--;}else{i++;}}out.println(sum);out.close();}static class Reader {final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;public Reader() {din = new DataInputStream(System.in);buffer = new byte[BUFFER_SIZE];bufferPointer = bytesRead = 0;}public Reader(String file_name) throws IOException {din = new DataInputStream(new FileInputStream(file_name));buffer = new byte[BUFFER_SIZE];bufferPointer = bytesRead = 0;}public String readLine() throws IOException {byte[] buf = new byte[64];int cnt = 0, c;while ((c = read()) != -1) {if (c == '\n') {break;}buf[cnt++] = (byte) c;}return new String(buf, 0, cnt);}public int nextInt() throws IOException {int ret = 0;byte c = read();while (c <= ' ') {c = read();}boolean neg = (c == '-');if (neg) {c = read();}do {ret = ret * 10 + c - '0';} while ((c = read()) >= '0' && c <= '9');if (neg) {return -ret;}return ret;}public long nextLong() throws IOException {long ret = 0;byte c = read();while (c <= ' ') {c = read();}boolean neg = (c == '-');if (neg) {c = read();}do {ret = ret * 10 + c - '0';} while ((c = read()) >= '0' && c <= '9');if (neg) {return -ret;}return ret;}public double nextDouble() throws IOException {double ret = 0, div = 1;byte c = read();while (c <= ' ') {c = read();}boolean neg = (c == '-');if (neg) {c = read();}do {ret = ret * 10 + c - '0';} while ((c = read()) >= '0' && c <= '9');if (c == '.') {while ((c = read()) >= '0' && c <= '9') {ret += (c - '0') / (div *= 10);}}if (neg) {return -ret;}return ret;}private void fillBuffer() throws IOException {bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);if (bytesRead == -1) {buffer[0] = -1;}}private byte read() throws IOException {if (bufferPointer == bytesRead) {fillBuffer();}return buffer[bufferPointer++];}public void close() throws IOException {if (din == null) {return;}din.close();}}}
