小红的数组

NC229976. 小红的数组

描述

小红拿到了一个长度为 $n$ 的数组，数组中的元素都是正整数。
小红想让你回答以下三个问题，取两个数乘积大于 $k$ 的方案数、取两个数乘积等于 $k$ 的方案数、取两个数乘积小于 $k$ 的方案数。
注：两个数是不放回且同时取的。例如对于数组[1,2,3,4,5]而言，取[1,2]和[2,1]我们认为是同一种方案。
但是，如果有两个数相等，那么取相等但位置不同的数不认为是同一种取法。例如对于数组[2,2,2,3]而言，有三种方案可以取到[2,2]。

输入描述

第一行输入两个正整数  和  ，用空格隔开。
第二行输入  个用空格隔开的正整数 ，用来表示数组。
数据范围：

输出描述

输出三个整数，用空格隔开。分别代表取两个数乘积大于  的方案数、等于  的方案数、小于  的方案数。

示例1

输入:

4 7
1 3 4 2

输出:

2 0 4

说明:

大于7的取数方案：[3,4]和[4,2]。小于7的取数方案：[1,3]、[1,4]、[1,2]、[3,2]

示例2

输入:

5 9
3 3 3 3 3

输出:

0 10 0

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3 解法, 执行用时: 977ms, 内存消耗: 37888K, 提交时间: 2022-06-21 15:14:34

from bisect import *

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
res = [0, 0, 0]
for i in range(n-1):
    l = bisect_left(a, k / a[i], i + 1, n)
    r = bisect_right(a, k / a[i], i + 1, n)
    res[0] += n - r
    res[1] += r - l
    res[2] += l - i - 1
print(*res)

上一题

下一题

详情