Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Warezovvv
 Аватар для Warezovvv
9 / 9 / 2
Регистрация: 09.12.2012
Сообщений: 219
30.01.2014, 12:13     Куски и ограниченные куски #1
Есть задание :
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");
    
}
Входные данные из примера работают правильно а из других тестов неправильно.
И мне кажется я не понял задание.
Можете подсказать что не так с функцией?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2014, 12:13     Куски и ограниченные куски
Посмотрите здесь:

Разобраться Куски программы Pascal
Имеется кусок ткани длиной М метров. От него последовательно отрезаются куски разной длины C++
C++ Объединить куски программы в единое целое
PHP Разбивка текста на куски по 4кб
Photoshop Разрезать на куски
Вырезать куски массива C++
Perl Дробление текста на куски, куски в переменные
Вытащить куски сайта PHP

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 20:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru