小红的数组【牛客tracker & 每日一题】

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

小红的数组

时间限制：1 秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小红拿到了一个长度为

n

n

n 的数组，数组中的元素都是正整数。

小红想让你回答以下三个问题，取两个数乘积大于

k

k

k 的方案数、取两个数乘积等于

k

k

k 的方案数、取两个数乘积小于

k

k

k 的方案数。

注： 两个数是不放回且同时取的。例如对于数组

[

1

,

2

,

3

,

4

,

5

]

[1,2,3,4,5]

[1,2,3,4,5] 而言，取

[

1

,

2

]

[1,2]

[1,2] 和

[

2

,

1

]

[2,1]

[2,1] 我们认为是同一种方案。但是，如果有两个数相等，那么取相等但位置不同的数不认为是同一种取法。例如对于数组

[

2

,

2

,

2

,

3

]

[2,2,2,3]

[2,2,2,3] 而言，有三种方案可以取到

[

2

,

2

]

[2,2]

[2,2]。

输入描述

第一行输入两个正整数

n

n

n 和

k

k

k，用空格隔开。

第二行输入

n

n

n 个用空格隔开的正整数

a

i

a_i

ai​，用来表示数组。

数据范围：

1

≤

n

≤

300000

,

1

≤

a

i

≤

10

9

,

1

≤

k

≤

10

18

1 \\le n \\le 300000, 1 \\le a_i \\le 10^9, 1 \\le k \\le 10^{18}

1≤n≤300000,1≤ai​≤109,1≤k≤1018

输出描述

输出三个整数，用空格隔开。分别代表取两个数乘积大于

k

k

k 的方案数、等于

k

k

k 的方案数、小于

k

k

k 的方案数。

示例

示例 1

输入：

4 7
1 3 4 2

输出：

2 0 4

说明： 大于 7 的取数方案：

[

3

,

4

]

[3,4]

[3,4] 和

[

4

,

2

]

[4,2]

[4,2]。小于 7 的取数方案：

[

1

,

3

]

[1,3]

[1,3]、

[

1

,

4

]

[1,4]

[1,4]、

[

1

,

2

]

[1,2]

[1,2]、

[

3

,

2

]

[3,2]

[3,2]。

示例 2

输入：

5 9
3 3 3 3 3

输出：

0 10 0

数据范围

• $1\le n\le 300000$
• $1\le a_i\le 10^9$
• $1\le k\le 10^{18}$

解题思路

本题是排序 + 双指针统计的经典计数问题。数组元素均为正整数，要求统计所有无序下标对

(

i

,

j

)

(i,j)

(i,j)（

i

<

j

i<j

i<j）中，两数乘积分别大于、等于、小于

k

k

k 的方案数。注意：若两个数相等但位置不同，仍视为不同方案，因此本质上是统计不同下标对的数量。

1. 问题等价转化

• 总下标对数量为 $$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}.$$
• 只需求出「乘积小于 $k$

2. 排序与双指针

将数组升序排序。由于元素均为正整数，固定左端点

i

i

i 后，乘积

a

i

⋅

a

j

a_i\\cdot a_j

ai​⋅aj​ 随

j

j

j 增大而单调不减，因此可以用双指针统计。

统计乘积小于

k

k

k 的方案数

l

s

ls

ls：

• 初始化右指针 $j=n$
• 从左到右枚举 $i=1,2,\dots ,n-1$
• 由于 $a_i$

统计乘积小于等于

k

k

k 的方案数

l

e

le

le：

• 重新初始化右指针 $j=n$
• 类似地，从左到右枚举 $i$
• 这样得到所有满足 $a_i\cdot a_j\le k$

3. 结果计算

由

l

e

le

le 与

l

s

ls

ls 可得：

e

q

=

l

e

−

l

s

,

eq=le-ls,

eq=le−ls,

g

t

=

n

(

n

−

1

)

2

−

l

e

.

gt=\\frac{n(n-1)}{2}-le.

gt=2n(n−1)​−le. 输出顺序为

g

t

,

e

q

,

l

s

gt,eq,ls

gt,eq,ls。

4. 复杂度分析

• 时间复杂度：排序 $O(n\log n)$
• 空间复杂度：需要存储数组，$O(n)$

总结

先将数组排序，利用正数乘积的单调性，用双指针分别统计「乘积小于

k

k

k」与「乘积小于等于

k

k

k」的方案数。二者相减得到乘积等于

k

k

k 的方案数，再用总对数减去「小于等于

k

k

k」的方案数得到「大于

k

k

k」的方案数。该方法避免了两两枚举，将计数复杂度从

O

(

n

2

)

O(n^2)

O(n2) 降至

O

(

n

log

⁡

n

)

O(n\\log n)

O(nlogn)，高效且能正确处理重复元素。

代码内容

#include <bits/stdc++.h>
using namespace std;

#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=300005;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ll n,k,a[N],i,j,gt,eq,ls;
scanf("%lld %lld",&n,&k);
for(i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+n+1);
j=n;
ls=0;
for(i=1;i<j;i++)
{
while(i<j&&a[i]*a[j]>=k) j—;
ls+=j–i;
}
j=n;
eq=0;
for(i=1;i<j;i++)
{
while(i<j&&a[i]*a[j]>k) j—;
eq+=j–i;
}
eq=eq–ls;
gt=n*(n–1)/2–eq–ls;
printf("%lld %lld %lld\\n",gt,eq,ls);
return 0;
}