E1-B

E1-B Hope Is the Thing With Feathers

题目描述

小A给出了n个正整数 $a_1$,…,$a_n$。

小A提出了q个问题。第i个问题中，小 A 会给出$d_i$,$k_i$，他想知道有多少$a_j(1\leq j \leq n)$满足$\lfloor \frac{a_j}{d_i}\rfloor=k_i$。

题目分析

满足$\lfloor\frac{a_j}{d_i}\rfloor=k_i$即满足$d_i k_i\leq a_j<d_i(k_i+1)$。

可以考虑寻找$d_i k_i$和$d_i(k_i+1)$，a数组中小于$d_i(k_i+1)$的数总频率减去小于$d_i k_i$的数总频率即为所求。

首先想到排序后二分查找，但是容易超时，注意到a的范围较小可以考虑利用计数排序统计频率得到pre数组。之后通过前缀和让pre[i]表示为小于等于i的数出现的频率和。

$a_i$最大值为1e6最小值为1。

求小于$d_i k_i$的数总频率

当a数组中所有数都小于$d_ik_i$时应取$pre[1e6]$，当a数组中所有数都大于$d_ik_i$时应取$pre[0]$，否则a数组中小于$d_ik_i$的数总频率即为$pre[d_ik_i-1]$，所以最后应取**$pre[max(0,min(d_ik_i,1e6+1)-1)]$**

求小于$d_i(k_i+1)$的数总频率

当a数组中所有数都小于$d_i(k_i+1)$时应取$pre[1e6]$ ，否则a数组中小于$d_i(k_i+1)$的数总频率为$pre[d_i(k_i+1)-1]$，所以最后应取**$pre[min(d_i(k_i+1),1e6+1)-1]$**

$pre[min(d_i(k_i+1),1e6+1)-1]-pre[max(0,min(d_ik_i,1e6+1)-1)]$即为所求

• 大数相加或相乘时可能会溢出注意使用1ll和long long
• 注意讨论$d_ik_i$较大的情况

示例代码

#include <stdio.h>
#define N 1001001
int n, q;
int a[N], pre[N];
long long int min(long long int a, long long int b)
{
    return a < b ? a : b;
}
long long int max(long long int a, long long int b)
{
    return a > b ? a : b;
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        pre[a[i]]++;
    }
    for (int i = 1; i < N; i++)
    {
        pre[i] += pre[i - 1];
    }
    while (q--)
    {
        int d, k;
        scanf("%d%d", &d, &k);
        int l = min(1ll * k * d, 1ll * N);
        int r = min(1ll * k * d + d, 1ll * N);
        printf("%d\n", pre[r - 1] - pre[max(0, l - 1)]);
    }
    return 0;
}