Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Warezovvv
9 / 9 / 2
Регистрация: 09.12.2012
Сообщений: 219
#1

Куски и ограниченные куски - C++

30.01.2014, 12:13. Просмотров 320. Ответов 0
Метки нет (Все метки)

Есть задание :
An integer K and a non-empty zero-indexed array A consisting of N integers are given.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A.
A bounded_slice is a slice in which the difference between the maximum and minimum values in the slice is less than or equal to K. More precisely it is a slice, such that max(A[P], A[P + 1], ..., A[Q]) − min(A[P], A[P + 1], ..., A[Q]) ≤ K.
The goal is to calculate the number of bounded_slices.
For example, consider K = 2 and array A such that:
A[0] = 3
A[1] = 5
A[2] = 7
A[3] = 6
A[4] = 3
There are exactly nine bounded_slices: (0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 4).
Write a function:
int solution(int K, int A[], int N);
that, given an integer K and a non-empty zero-indexed array A of N integers, returns the number of bounded_slices of array A.
If the number of bounded_slices is greater than 1,000,000,000, the function should return 1,000,000,000.
For example, given:
A[0] = 3
A[1] = 5
A[2] = 7
A[3] = 6
A[4] = 3
the function should return 9, as explained above.
Assume that:
N is an integer within the range [1..100,000];
K is an integer within the range [0..1,000,000,000];
each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.


Я написал к нему код:
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
#include <vector>
#include <iostream>
using namespace std;
int solution(int K, vector<int> &A) {
    int P;
    int Q;
    int countSlices=0;
    for(int min=0;min<A.size();min++){
        for(int max=min;max<A.size();max++){
            P=min;
            Q=max;
            if(A[Q]-A[P]<=K&&max-min<K){
                countSlices++;          
            }
            else{
                break;
            }       
        }
    }   
    cout<<countSlices;
    return countSlices;
}
int main(){
    vector<int> v;
    //6, [4, 5, 8, 5, 1, 4, 6, 8, 7, 2, 2, 5
    v.push_back(6);
    v.push_back(5);
    v.push_back(8);
    v.push_back(5);
    v.push_back(1);
    v.push_back(4);
    v.push_back(6);
    v.push_back(8);
    v.push_back(7);
    v.push_back(2);
    v.push_back(2);
    v.push_back(5);
    int K=2;
    solution(K,v);
    system("pause");
    
}
Входные данные из примера работают правильно а из других тестов неправильно.
И мне кажется я не понял задание.
Можете подсказать что не так с функцией?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2014, 12:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Куски и ограниченные куски (C++):

Вырезать куски массива - C++
Помогите, пожалуйста, решить программы на си++, если не решу мне хана, заранее спасибо: Дан одномерный массив А, состоящий из N различных...

Объединить куски программы в единое целое - C++
добрый день есть следующее задание: &quot;ПОИСК БИТОВОГО ОБРАЗА&quot;. Вводится последовательность строк символов не длиннее 16 символов....

Имеется кусок ткани длиной М метров. От него последовательно отрезаются куски разной длины - C++
Имеется кусок ткани длиной М метров. От него последовательно отрезаются куски разной длины. Все данные по использованию ткани заносятся в...

Ограниченные массивы - C++
Ограниченным называется массив, у которого оператор проверяет индекс на принадлежность диапазону. Логику проверки я могу сделать, а какой...

Дробление текста на куски, куски в переменные - Perl
Добрый день, запутался совсем с решением задачи. Имеется текст, структура текста повторяющаяся, напоминает повторяющиеся элементы с...

Разрезать на куски - Photoshop
Здравствуйте подскажите как разрезать на 100 равных кусков область что синего цвета. Резать нужно по часовой стрелки.

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2014, 12:13
Привет! Вот еще темы с ответами:

.NET 3.x Деление текста на куски - Visual Basic .NET
Всем доброго дня! Необходимо разделить текст на куски, по 2000 символов. Навоял такой код....по логике должен работать...Первые два...

Разобраться Куски программы - Pascal
Нужны куски программы на паскале 1)Нахождения N степени числа. Число и степень вводим с клавиатуры. 2)Даны два числа....

Объединить куски кода - PHP БД
ребята, добрый день! подскажите, пожалуйста, как объединить эти два кода в один? очень надо, чтобы здесь $file =...

Вытащить куски сайта - PHP
Всем привет, как то давно я писал обычные сайты в 1 страницу, а тут приспичило вспомнить былое и добавить новых знаний. Играю в игру и в...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru