C program 002

The range minimum query (RMQ) problem looks as follows: You are given a list of n numbers and a sequence of queries. Each query is a pair of integers (L,R) such that 1 <= L <= R <= n. The answer to the query is the minimum of the values that occur in the list at (1-based) positions L through R, inclusive.

For example, if the list is (3,1,4,2,5), then:

• The answer to the query (1,2) is min(3,1)=1
• The answer to the query (2,4) is min(1,4,2)=1
• The answer to the query (4,5) is min(2,5)=2
  
  Assume: n<=50

Input and Output Format:

The first line of the input consists of an integer that corresponds to n, the number of elements in the list.

The next line of the input consists of the n integers in the list. The numbers in the list are separated by a space.

The next line of the input consists of k that corresponds to the number of range queries.

The next k lines of the input consists of 2 integers Li and Ri that correspond to L and R of each range query.

The output consists of k integers that correspond to the result of k queries.

Sample Input:

5

3 1 4 2 5

3

1 2

2 4

4 5

Sample Output:

1

1

2

Solution Code :

#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a[n],r,b,c,min;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    scanf("%d",&r);
    while(r--)
    {
        scanf("%d %d ",&b,&c);
        min=a[b];
        for(int i=b;i<=c;i++)
        {
            if(a[i]<min)
            min=a[i];
        }
        printf("%d\n",min);
    }
    return 0;
}

Baca juga