3607. Сортировка по росту

На торжественном открытии олимпиады, впрочем, как и на её закрытии, спортсмены каждой страны были одеты в одинаковые олимпийские костюмы. Естественно, что при таком большом количестве спортсменов, тренеров и обслуживающего персонала, для многих стран сам процесс пошивки олимпийской парадной формы был довольно ответственным и важным делом, и поэтому необходимо было знать рост каждого члена делегации для пошивки формы соответствующего размера. Фирмам, которые будут заниматься пошивом парадной формы, частично повезло, так как известно, что ни в одной делегации не было членов делегации ростом ниже полутора метров и выше двух с половиной.

У вас в распоряжении имеется база данных, в которую занесены рост каждого члена делегации по соответствующему виду спорта. Ваша задача быстро отвечать на запросы типа: А сколько членов делегации имеют рост в пределах от a до b сантиметров включительно?

Вход. Первая строка каждого запроса содержит единственное число n (1 ≤ n ≤ 20000) – количество членов соответствующей делегации. Во второй строке запроса содержится n целых чисел, разделённых единичным пробелом – рост соответствующего члена делегации в сантиметрах. Данные о росте не отсортированы, так как помещались в базу данных в последний момент и не были поэтому обработаны. Третья строка запроса содержит собственно сам запрос: 2 числа – нижняя и верхняя границы интересующего фирму – изготовитель ростового интервала.

Выход. Для каждого запроса в отдельной строке выведите ответ на него.

Пример входа	Пример выхода
7 153 168 155 167 155 167 155 165 170 6 189 191 169 190 192 191 165 172	3 1

РЕШЕНИЕ

массив

Анализ алгоритма

Считываем рост членов делегаций в линейный массив. Затем проходим по нему, подсчитывая количество элементов в промежутка от a до b включительно.

Реализация алгоритма

Объявим массив для хранения роста членов делегаций.

#define MAX 20010

int m[MAX];

Читаем входные данные. Обрабатываем несколько тестов.

while(scanf("%d",&n) == 1)

{

for(i = 0; i < n; i++) scanf("%d",&m[i]);

scanf("%d %d",&a,&b);

В переменной cnt подсчитываем количество элементов m[i] в промежутке от a до b включительно.

for(cnt = i = 0; i < n; i++)

if ((m[i] >= a) && (m[i] <= b)) cnt++;

Выводим ответ.

printf("%d\n",cnt);

}

Реализация массива на указателях

#include <stdio.h>

int i, n, a, b, cnt;

int *m;

int main(void)

{

while(scanf("%d",&n) == 1)

{

m = new int[n];

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

scanf("%d %d",&a,&b);

for(cnt = i = 0; i < n; i++)

if ((m[i] >= a) && (m[i] <= b)) cnt++;

printf("%d\n",cnt);

delete [] m;

}

return 0;

}

Реализация массива на векторе

#include <cstdio>

#include <vector>

using namespace std;

int i, n, a, b, cnt;

vector<int> m;

int main(void)

{

while(scanf("%d",&n) == 1)

{

m.resize(n);

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

scanf("%d %d",&a,&b);

for(cnt = i = 0; i < n; i++)

if ((m[i] >= a) && (m[i] <= b)) cnt++;

printf("%d\n",cnt);

}

return 0;

}

Java реализация TLE, медленный Scanner

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

while(con.hasNextInt())

{

int cnt, i, n = con.nextInt();

int m[] = new int[n];

for(i = 0; i < n; i++)

m[i] = con.nextInt();

int a = con.nextInt();

int b = con.nextInt();

for(cnt = i = 0; i < n; i++)

if ((m[i] >= a) && (m[i] <= b)) cnt++;

System.out.println(cnt);

con.close();

}

}

}

Java реализация через BufferedReader

import java.util.*;

import java.io.*;

public class Main

{

public static void main(String[] args) throws IOException

{

BufferedReader read =

new BufferedReader(new InputStreamReader(System.in));

//BufferedReader read =

// new BufferedReader(new FileReader ("3607.in"));

while(read.ready())

{

int cnt = 0, i, n = Integer.parseInt(read.readLine());

int mas[] = new int[n];

String s[] = read.readLine().split(" ");

for(i = 0; i < n; i++)

mas[i] = Integer.parseInt(s[i]);

s = read.readLine().split(" ");

int a = Integer.parseInt(s[0]),

b = Integer.parseInt(s[1]);

for(i = 0; i < n; i++)

if ((mas[i] >= a) && (mas[i] <= b)) cnt++;

System.out.println(cnt);

}

}

}