题解 P1296 【奶牛的耳语】

北北北北 · 2019-10-11 09:57:17 · 题解

1.先对奶牛的位置进行升序排序

2.将每头奶牛所在的位置设为区间的左端点，将每头奶牛所在的位置加上声波最远所能发送的距离的和设为区间的右端点，这样我们就得到了一个关于声波发送的有效范围

3.通过上面所求出来的声波发送的有效范围即可来判断下个奶牛所在的位置是否能和当前这个奶牛相互交流，若能则答案数加一，反之就停止判断，因为奶牛所在的位置是按升序排序的，若当前这个条件不满足，则可以知道这个奶牛所在的位置是大于声波发送的有效范围的最大值的，此时就应该停止判断，以提高效率(不加这个的话，最后两个点会超时)

#include <stdio.h>
#include <stdlib.h>

int a[1000010];

int cmp(const void *a,const void *b)
{
      return *(int*)a-*(int*)b;
}

int main(void)
{
      int i,j,n,d;
      int count = 0;

      scanf("%d %d", &n,&d);
      for(i = 0; i < n; i++)
      {
           scanf("%d", &a[i]);
      }
      qsort(a,n,sizeof(a[0]),cmp);
      for(i = 0; i < n; i++)
      {
          for(j = i+1; j < n; j++)
          {
               //a[j]为元素,a[i]为区间的左端点,a[i]+d为区间的右端点

               if(a[j] >= a[i] && a[j] <= a[i]+d) //判断该元素是否在该区间内，若在则能相互交流，反之不能相互交流且终止搜索(因为元素是按升序来排列的，所以当这个条件不满足时，则该元素一定是大于该区间的右端点，即最大值)
               {
                      count++;
               }
               else
               {
                      break;
               }
          }
      }
      printf("%d", count);

      return  0;
}