爬山(ACM签到题)

小Z准备去爬山,在他的面前有N座山,每座山都有对应的高度。他想选择两座高度差最小的山进行攀爬。但由于好多山之间的高度差可能是相同的,所以他需要你告诉他高度差最小的两座山的高度差是多少以及有多少种不同的选取方式(选取山A、B和选取山B、A视为同一种选取方式)。

Input

输入一个T,代表数据的组数。(T<=10)
每组数据包含一个N,代表有多少座山。(2<=N<=100,000)
接下来一行包括N个数,分别表示每座山的高度x(1<=x<=1000,000,000)。

Output

对于每组测试样例,输出一行,包含两个整数,代表两座山最小的高度,以及有多少种不同的方式选取两座山。两个数之间用一个空格隔开,每个测试样例占一行。

#include<stdio.h>
#define SWAP(a,b) {int temp;temp=a;a=b;b=temp;}  // 交换两个int值
void quick_sort_sub(int*data, int left, int right);  // 快速排序的肉
void quick_sort(int*data, int data_size);  // 快速排序的皮

int main(void)
{
  int i = 0;  
  int T = 0;  // 数据的组数
  scanf("%d", &T);
  int minimum[10] = { 0 }, minimum_number[10] = { 0 };  // 最小的差值及可能方式的数量
  for (int time = 0; time < T; time++)  //外层循环(组数)
  {
    int high[100] = { 0 };  // 每座山的高度
    int N = 0;  // 山的数量
    scanf("%d", &N);
    i = 0;
    while (i < N)
    {
      scanf("%d", &high[i]);
      i++;
    }
    quick_sort(high, N);  // 快排
    int j = 1;
    int sub;  // 两座山的高度差
    int min = sub = high[j] - high[j - 1];; // 设最小值为第一座山和第二座山的高度差
    int same = 0;  // 相同高度的山的数量
    if (min == 0)  // 当第一座山和第二座山高度相同时
    {
      while (j < N)
      {
        if (min == 0)
        {
          minimum_number[time] = 0;
          same = 1;
          for (; j<N ; j++)
          {
            if (high[j] == high[j - 1])
            {
              minimum_number[time] += same;
              same++;
            }
            else
              same = 1;
          }
        }

      }
      minimum[time] = 0;
    }
    else  // 当前两座山高度不相同时
    {
      while (j < N)
      {
        if ((sub = high[j] - high[j - 1]) < min)
        {
          min = sub;
          minimum_number[time] = 1;
        }
        if (sub == min)
          minimum_number[time]++;
        j++;
      }
      minimum[time] = min;
    }

  }
  for (i = 0; i < T; i++)
    printf("%d %d\n", minimum[i], minimum_number[i]);

  return 0;
}

void quick_sort_sub(int*data, int left, int right)
{
  int left_index = left;
  int right_index = right;
  int pivot = data[(left + right) / 2];

  while (left_index <= right_index)
  {
    for (; data[left_index] < pivot; left_index++)
      ;
    for (; data[right_index] > pivot; right_index--)
      ;
    if (left_index <= right_index)
    {
      SWAP(data[left_index], data[right_index]);
      left_index++;
      right_index--;
    }
  }

  if (right_index > left)
  {
    quick_sort_sub(data, left, right_index);
  }
  if (left_index < right)
  {
    quick_sort_sub(data, left_index, right);
  }
}

void quick_sort(int*data, int data_size)
{
  quick_sort_sub(data, 0, data_size - 1);
}

另外,由于这道题重点不在排序。只是我随便拿了个之前写的快速排序,所以在快速排序部分就不写注释了,嘻嘻

还有,本题应该要用long long 但鉴于我也不玩ACM,那就只要我看着就得对就对,是吧~

说点什么

avatar

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

  Subscribe  
提醒