题解 P1296 【奶牛的耳语】

· · 题解

看了其他题解. 觉得有必要把这个问题说清楚, 简单化.

思路清晰的情况下, 这题根本没难度.

其他题解里, 凡是出现 结果++; 都是没好好理解题意.

原理如下, 如果限定距离 d=100 , 举例, 并排序后:

11 23 37 255 266 277 366 1024 1035 1046

设置一个 i 循环作为主循环 , 然后设置一个开始位置 s=0

这样当 i=[4] 到达 255 的时候, 前面3项距离都超过100 ,

这时候通过 s++ 寻找左边d<=100的数, s自然就到达[4]

然后 i 到达 266,277 的时候, 只需要和s=[4]比较一次便可.

在i和s之间的所有数字都满足距离小于d的条件.

所以 t += i - s;

i去到366的时候呢? s位置255不满足了, 这时候s++ 到达266, 又满足条件了.

总的说来, i单独最多循环n次, s单独循环n次, 并非嵌套循环, 所以循环次数仅仅为2n

相对于前面的排序的复杂度, 在超大数据下, 这个2n是几乎可以忽略的. 


#include <algorithm>
#include <iostream>
using namespace std;

int nums[1000001];

bool compi(int& v1, int& v2)
{
    return v1 < v2;
}

int main()
{

    int n, d;
    scanf("%d%d", &n, &d);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &nums[i]);
    }

    //题目数据未排序, 需要排一下
    sort(nums, nums + n, compi);

    int s = 0;//表示左边最后在范围内的另外一只牛的位置

    int t = 0;//结果

    //循环右边的牛
    for (int i = 0; i < n; i++)
    {
        int curr = nums[i];

        //检查左边的另外一只牛在不在范围
        //如果不在, 则继续寻找
        //最差的情况是 因为 s==i 而结束循环, 一个都找不到.
        for (; s < i; s++)
        {
            //如果找到一只牛是在范围内, 则其他牛全都在范围内
            if (curr - nums[s] <= d)
            {
                //范围内, 除了自己, 所有符合结果的牛的个数
                t += i - s;

                //找到了, 就让s停留在当前位置
                break;
            }
        }
    }

    cout << t;

    return 0;
}