小红书笔试8.28 第二题【排序+双指针】

其他题目都有大佬写过了，我只分享一下第二题的一种解法。

法术

时间限制：3000MS
内存限制：589824KB

题目描述：

小明是一名魔法师，他会n种法术，其中第种法术的威力为aj，他经常通过双手各自释放一种法术来提升威力，能得到的威力值为双手各自释放的法术的威力的乘积，但是他还不够强大，双手释放的两种法术必须是不同的，即不能双手释放同一种法术。这天他接到了一个任务，需要释放威力值至少为K才能完成，他想请你帮他算一算，在两只手都释放法术的情况下，共有多少方案能达到威力值K。每种方案可记作(u，v)，uV，其威力值为ay*ay, (u， v)和(v， u)会被视为不同的方案。

输入描述

第一行两个正整数n和K，表示法术数量和威力值需求。
第二行为n个正整数a1，a2……an，其中a，表示第i个法术的威力为a。

输出描述

输出威力值至少为K的方案数。

样例输入

3 3
3 2 1

样例输出

4

提示

1 <= n <= 30000, 1 <= K <= 10^16, 1 <= ai <= 10^9

【排序+双指针】
左指针left从0向后走，右指针right从n-1向前走。
记mul = a[left] * a[right]，
-若mul >= k，说明a[right]与[left...right]之间的所有数相乘都满足>=k。
-若mul < k，说明左指针太小了，需要右移。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long k = scanner.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextLong();
        }
        Arrays.sort(a);
        int left = 0, right = n - 1;
        long ans = 0;
        while (left < right) {
            long mul = a[left] * a[right];
            if (mul >= k) {
                ans += right - left;
                --right;
            } else {
                ++left;
            }
        }

        System.out.println(ans * 2);
    }
}