Для данного массива размера 'n' найдите элемент max в каждом окне размера 'k' и добавьте их все, затем выведите общую сумму в качестве выходных данных. - PullRequest
Новая
       12

Для данного массива размера 'n' найдите элемент max в каждом окне размера 'k' и добавьте их все, затем выведите общую сумму в качестве выходных данных.

0 голосов
/ 05 октября 2019

Пока это мой код. Раньше у меня была проблема, когда я игнорировал последний элемент основного массива, но затем я запустил код в отладчике и исправил его.

Он отлично работает для примеров тестовых случаев и некоторыхпользовательские тесты, которые я случайно дал. Но я все еще получаю вердикт «НЕПРАВИЛЬНЫЙ ОТВЕТ», когда я отправляю код.

Я стараюсь избегать любых встроенных функций, таких как sort или что-то еще, чтобы максимально сократить сложность времени.

До сих пор я пробовал код с 14 различными тестами. Это дало правильный вывод всем им. Кроме того, нет необходимости изменять типы int на long или что-то еще, поскольку ограничения находятся в пределах границ int.

Любая помощь в поиске ошибки в моем коде будет принята с благодарностью!

(я также включил примерные входы и соответствующие выходы в конце кода) 

#include <cmath>
#include <stdio.h>
#include <iostream>
#include <set>
using namespace std;

int main() {
    int t=0;
    cin>>t;

    for(int z=0;z<t;z++){
        int n=0,k=0;
        scanf("%d%d",&n,&k);

        int arr[n];
        int sum=0;

        for(int i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        int maxx=0;
        int ind=0;
        int tindex=k;

        for(int i=0;i<k;i++){
            if(arr[i]>maxx){
                maxx=arr[i];
                ind=i;
            }
        }
        sum+=maxx;

        int tmax=0;
        for(int i=k;i<n;){
            if(ind>0){
                sum+=max(maxx,arr[i]);
                if(arr[i]>tmax){
                    tmax=arr[i];
                    tindex=i;
                }
                ind--;
                i++;
            }
            else{
                ind=(tindex%k)+1;
                maxx=tmax;
                tmax=0;
            }
        }
        cout<<sum<<endl;
    }
}

Примерный ввод 

2
7 3
4 10 54 11 8 7 9 
4 2
11 15 12 9

Примерный вывод 

182
42

1 Ответ

0 голосов
/ 05 октября 2019

Простой тестовый пример: 

1
4 2
5 4 3 2

Правильный ответ 12, Ваш код печатает : 11

max(5, 4) + max(4, 3) + max(3, 2) = 12

В основном, как вы рассчитываетеmaxx недопустимо и упрощенно.
Простое, но медленное решение, имеет O(n * k) сложность времени и O(n) сложность памяти (для сохранения всех данных). Вы должны начать с этого.
Более сложное, но быстрое решение имеет O(n) сложность по времени и O(k) сложность памяти (для хранения только данных окна).

...