CCF certification - 201712-1 minimum difference (C + +)

CCF certification - 201712-1 minimum difference

Test number 201712-1
Title of test paper Minimum difference
Time limit 1.0s
Memory limit 256.0MB
Problem description Problem description
   given n numbers, please find the two numbers with the smallest difference (absolute value of difference) and output the absolute value of their difference.
Input format
   the first line of the input contains an integer n. The second line contains n positive integers separated by a space.
Output format
   output an integer to indicate the answer.
sample input
  5
  1 5 4 8 20
sample output
  1
Sample explanation
The two numbers with the smallest difference are 5 and 4, and the difference between them is 1.
sample input
  5
  9 3 6 1 3
sample output
  0
Sample explanation
          has two identical numbers 3, and the difference between them is 0.
Data size and engagement
   for all evaluation cases, 2 ≤ n ≤ 1000, each given integer is a positive integer not more than 10000.

The simplest way: Violence Law
The data is stored in an array. Because it is an indefinite number of arrays, it is defined as a dynamic array. Then the data in the array is sorted to get the absolute value of the final minimum difference. The C + + code is as follows:

#include<iostream>
using namespace std;
int n; //n represents the number of input data 
int *array;//Represents an array of stored data (dynamic array)

//Get the absolute value of the difference between two data 
int difference(int a, int b)
{
    if(a>=b) return a-b;
    else return b-a; 
}

int Min()
{
    int min=difference(array[1],array[0]);
    int Diff=0;
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            Diff=difference(array[i],array[j]);
            if(Diff<min) 
                min=Diff; 
        }
    }
    return min;
}

int main()
{
    cin>>n;
    array=new int[n];//Give a certain space to an array
    for(int i=0;i<n;i++)
    {
        cin>>array[i];
    }
    cout<<Min();
    return 0;
}

Another method is to sort the input row of data from small to large, and then take the difference value of the adjacent elements before and after (usually the latter element minus the former one, and keep the difference value positive), and then take the minimum value of these differences. The code is as follows:

#include<iostream>
using namespace std;
int n;
int *array;

int difference(int a, int b)
{
    return b-a;
}

int Min()
{
    int min=array[1]-array[0];
    int Diff=0;
    for(int i=1;i<n-1;i++)
    {
        Diff=array[i+1]-array[i];
        if(Diff<min) min=Diff;
    }
    return min;
}

int main()
{
    cin>>n;
    array=new int[n];
    for(int i=0;i<n;i++)
    {
        cin>>array[i];
    }
    int i,j,temp;
    for(i=1;i<n;i++)//Insertion sort
    {
        temp=array[i];
        for(j=i;(j>0)&&(temp<array[j-1]);j--)
            array[j]=array[j-1];
        array[j]=temp;
    }       
    cout<<Min();
    return 0;
}

Posted on Fri, 03 Apr 2020 09:33:19 -0700 by rea|and