• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Spoj zwraca limit time extended {c#}

VPS Starter Arubacloud
0 głosów
293 wizyt
pytanie zadane 1 kwietnia 2022 w SPOJ przez chrystian Gaduła (4,780 p.)
zmienione kategorie 1 kwietnia 2022 przez ScriptyChris

zadanie Arraysub  zwraca mi time limit exceeded a   jak poprwawić pogram by nie zwracał błedu 

using System;
using System.Linq;

namespace ConsoleApp17
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            int n = Convert.ToInt32((Console.ReadLine()));

            int k;

            int val = 0;

            int[] arr = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
            k = Convert.ToInt32((Console.ReadLine()));

            for (int i = 0; i < n - k + 1; i++)
            {
                val = arr[i];
                for (int j = i; j < i + k; j++)
                {
                    if (val < arr[j])
                    {
                        val = arr[j];
                    }
                }

                Console.Write(val + " ");
            }
        }
    }
}

 

1 odpowiedź

0 głosów
odpowiedź 2 kwietnia 2022 przez Whistleroosh Maniak (56,900 p.)
wybrane 5 kwietnia 2022 przez chrystian
 
Najlepsza
Twój algorytm działa teraz w złożoności O(nk), więc to zdecydowanie za wolno. Możesz spróbować rozwiązać to szybciej korzystając z seta albo kolejki monotonicznej.
komentarz 5 kwietnia 2022 przez chrystian Gaduła (4,780 p.)

coś takiego pomoże czy nie


            C(9,new int[]{1,2,3,1,4,5,2,3,6},3);
        

        private static void C(int n, int[] arr, int k)

        {
            int val = 0;
            for (int i = 0; i < n - k + 1; i++)
            {
                val = arr[i];
                for (int j = i; j < i + k; j++)
                {
                    if (val < arr[j])
                    {
                        val = arr[j];
                    }
                }

                Console.Write(val + " ");
            }
        }

 

komentarz 5 kwietnia 2022 przez Whistleroosh Maniak (56,900 p.)
Niestety nie. To wciąż jest O(nk)
komentarz 8 kwietnia 2022 przez chrystian Gaduła (4,780 p.)
@Whistleroosh podeślesz jakiś example bym wiedział o co chodzi
komentarz 8 kwietnia 2022 przez Whistleroosh Maniak (56,900 p.)

Musisz albo skorzystać ze struktury danych set. Która jest już nawet zaimplementowana w c#. Albo z kolejki monotonicznej

komentarz 8 kwietnia 2022 przez chrystian Gaduła (4,780 p.)

@Whistleroosh dobrze myslę 

     HashSet<int> oddNumbers = new HashSet<int>(n);

i później

for oddnumver,add

i

array copy

 

komentarz 8 kwietnia 2022 przez Whistleroosh Maniak (56,900 p.)
Nie bardzo rozumiem o co chodzi w drugiej i trzeciej linijce. Ale uświadomiłem sobie, że źle Ci powiedziałem, musisz przecież trzymać wielokrotne wystąpienia tej samej liczby, więc nie możesz korzystać z seta a musisz skorzystać z multiseta

Podobne pytania

0 głosów
2 odpowiedzi 934 wizyt
pytanie zadane 5 września 2017 w C i C++ przez J0ker Pasjonat (15,400 p.)
0 głosów
2 odpowiedzi 793 wizyt
pytanie zadane 17 sierpnia 2018 w SPOJ przez Marcin Rasta Pawłows Użytkownik (600 p.)
0 głosów
0 odpowiedzi 236 wizyt
pytanie zadane 24 sierpnia 2020 w SPOJ przez magda_19 Gaduła (3,080 p.)

92,455 zapytań

141,263 odpowiedzi

319,100 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...