Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
3 / 0 / 0
Регистрация: 10.10.2014
Сообщений: 5

Минимальное значение массива на отрезке от L до R

10.10.2014, 19:30. Показов 2102. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
В первой строке входа даны два числа n и m (1≤n,m≤10^5), во второй строке — n целых чисел, задающих начальные значения массива. Далее даны m строк вида Set I X, где I — номер позиции, а X — новое значение, или Min L R, где L и R — левая и правая границы отрезка. Для каждой операции Min программа должна вывести минимальное значение на отрезке от L до R. Позиции нумеруются от единицы до n, все значения — натуральные числа, не превышающие 10^9.

Sample Input:
5 7
1 2 3 4 5
Min 1 5
Set 1 8
Min 1 5
Min 1 1
Min 1 3
Set 3 1
Min 2 4

Sample Output:
1
2
8
2
1

В условиях требовалось еще все это реализовать в виде дерева отрезков, проверка автоматическая.
Поэтому меня устроит просто поиск минимального элемента на отрезке любым способом, но мой код валится на 2-м тесте (в качестве первого идет пример из условий задачи - он отрабатывает нормально), подскажите где у меня ошибка.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
 
int main( )  {
  vector <int> arr;
  vector <int>::iterator start, end, location;
 
   
   int n = 0;  
   int m = 0;   
   int i = 0;
   int j = 0;
   int k = 0;
   int num = 0;
   string s = "";
 
   cin >> n >> m;
   
   for ( i = 1; i <= n; i = i + 1 ) {     
    cin >> num;
    arr.push_back(num);
   }
 
   for ( i = 1; i <= m; i = i + 1 ) {     
         cin >> s >> j >> k;
         if ( s == "Min" ) {             
              start = arr.begin() + (j-1);
              //advance( start, j-1 );              
              end = arr.begin() + (k-1);
              //advance( end, k-1 );             
              location = min_element(start, end) ;
              cout << *location << endl;                 
         }
         else if ( s == "Set" ) {
            arr[j-1] = k;                           
         }
   }
   
  return 0;    
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
10.10.2014, 19:30
Ответы с готовыми решениями:

Найти минимальное значение функции на отрезке до ее первого отрицательного значения: Y=3sin(x+5) на отрезке [-5;3] с шаг
Найти минимальное значение функции на отрезке до ее первого отрицательного значения: Y=3sin(x+5) на отрезке с шагом 0.25 Добавлено...

Минимальное значение функции на отрезке
Помогите с задачкой...не могу понять как её реализовать... Найти минимальное значение функции на отрезке .

Найти минимальное значение функции на отрезке
Найти минимальное значение функции на отрезке до её первого отрицательного значения Y=3sin(x+5) на отрезке с шагом 0.25

4
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
10.10.2014, 19:50
ошибка в том что надо написать дерево отрезков.

ну или что-нибудь другое быстрее чем просто проход по отрезку.
0
3 / 0 / 0
Регистрация: 10.10.2014
Сообщений: 5
10.10.2014, 20:02  [ТС]
> ошибка в том что надо написать дерево отрезков.
> ну или что-нибудь другое быстрее чем просто проход по отрезку.

Нет, в случае превышения времени выполнения система выдает ошибку типа "Failed test #4. Time limit exceeded"
у меня же "Failed test #2. Wrong answer".
Т.е. ошибка в неправильной выдаче результата, со временем - все ок.
К сожалению, тесты не разглашаются.
Поэтому я и уточнил у сообщества, может кто-нибудь увидит ошибку в моем коде?
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
10.10.2014, 20:17
rodo, кажется min_element (да и другие алгоритмы) принимает полуинтервал [) а не отрезок [].
Ну это все равно же упадет по времени.

а блин. а как тогда 1 тест прошел? тогда не знаю

Добавлено через 5 минут
а да в этом косяк. просто непонятно че он выведет если пустой отрезок дать.

если дать полуинтервал (iter, iter) то он возвратит iter.
0
3 / 0 / 0
Регистрация: 10.10.2014
Сообщений: 5
10.10.2014, 20:31  [ТС]
> min_element (да и другие алгоритмы) принимает полуинтервал [) а не отрезок [].

спасибо огромное, тест сдан.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
10.10.2014, 20:31
Помогаю со студенческими работами здесь

Найти максимальное/минимальное значение функции на отрезке.
Как решаются задания типа: &quot;найти максимальное/минимальное значение y=x^4-2x^2+5 на x\in ???

Найти максимальное и минимальное значение функции на отрезке
y=2^x y=x^2-4x+6

Найти минимальное и максимальное значение функции на отрезке [a; b]
Всем доброго времени суток! Задали лабораторную работу, где необходимо вычислить n значений функции на отрезке . Среди вычислительных...

Найти максимальное/минимальное значение функции на отрезке
Функция y = f (x) определена на промежутке и имеет производную в каждой точке области значение. На рисунке изображена график функции y = f...

Найти максимальное и минимальное значение функции на отрезке
Для заданной функции f=x2(x-3) найти максимальное и минимальное значение функции на отрезке с точностью ∆x=h., a=5, b=15, ∆x...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt
8Observer8 05.04.2026
Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru