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;
}

Recommended

Post a Comment