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

zadanie bierki

VPS Starter Arubacloud
0 głosów
234 wizyt
pytanie zadane 14 stycznia 2023 w C i C++ przez polandonion Mądrala (6,970 p.)
edycja 14 stycznia 2023 przez polandonion

Siema, robie to zadanie juz 10. raz i mi nie wchodzi. powie ktos czemu w niektorych testach wypluwa mi liczbe o 1 za duza?

zadanie: https://szkopul.edu.pl/problemset/problem/KiEvCpZBaUNRCp6oTZx2oAQ4/site/?key=statement

kod:

#include <iostream>
#include <algorithm>

using namespace std;

int bie[30000];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	for (int *i = bie; i < bie + n; i ++)
		cin >> *i;

	sort(bie, bie + n);

	int *l = bie, *r = bie + 2, mx;
	mx = (*l + *(l + 1) > *r ? 3 : 0);

	while (r < bie + n) {
		if (*l + *(l + 1) > *r) {
			r ++;
			if (r < bie + n)
				mx = max(mx, int(r - l + 1));
		}
		else
			l ++;

		if (int(r - l) < 2)
			r ++;
	}
	cout << mx;
}

 

2 odpowiedzi

+2 głosów
odpowiedź 14 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Niezbyt rozumiem ten twój kod, ale mogę Ci powiedzieć jak to powinno się zrobić. Masz 2 sposoby jeden w O(n log n), a drugi sprytniejszy w O(n). masz 2 wskazniki jeden lewy a drugi prawy liczby pomiedzy lewy i prawy lacznie traktujesz jako na przedziale, który jest w gąsienicy. I teraz trzymasz wszystkie liczby pomiędzy na multisecie i jak zastanawiasz się czy przesunąć to korzystasz z nierówności trójkąta. suma dwóch najmniejszych musi być większa niż sprawdzany. I Wtedy masz O(n log n), możesz też zamiast seta trzymać poprostu 2 wskazniki korzystając z tego, że najmniejsze to lewy wsk i sprawdzasz tylko te 2 najmniejsze. Niewiem, czy robisz to samo, czy cos innego, bo niezbyt kumam twoj kod.
2
komentarz 14 stycznia 2023 przez Whistleroosh Maniak (56,900 p.)
Kod robi mniej więcej to samo, ale jest mało czytelny przez niepotrzebną arytmetykę na wskaźnikach
0 głosów
odpowiedź 14 stycznia 2023 przez Whistleroosh Maniak (56,900 p.)

Problemy w indeksach. Poprawiona wersja:

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int bie[30000];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n;
    cin >> n;
 
    for (int *i = bie; i < bie + n; i ++)
        cin >> *i;
 
    sort(bie, bie + n);
 
    int *l = bie, *r = bie + 2, mx;
    mx = (*l + *(l + 1) > *r ? 3 : 0);
    r++;

    while (r < bie + n) {
        if (*l + *(l + 1) > *r) {
            r ++;
            mx = max(mx, int(r - l));
        }
        else
            l ++;
 
        if (int(r - l) < 3)
            r ++;
    }
    cout << mx;
}

 

komentarz 14 stycznia 2023 przez polandonion Mądrala (6,970 p.)

dzięki, działa, tylko w tej linii:

if (int(r - l) < 3)

powinno być:

if (int(r - l) < 2)

Bo wyobraź sobie taką sytuację. Właśnie wykonał się else, czyli wskaźnik lewy ++. i załóżmy, że po tej operacji l = 3 i r = 5. Twój if się wykona, a nie wiadomo, czy od tego fragmentu nie zaczyna się najdłuższy ciąg.

1
komentarz 14 stycznia 2023 przez Whistleroosh Maniak (56,900 p.)
Tak, racja

Podobne pytania

0 głosów
1 odpowiedź 108 wizyt
pytanie zadane 16 czerwca 2023 w Algorytmy przez nerfiko Nowicjusz (170 p.)
+1 głos
1 odpowiedź 179 wizyt
pytanie zadane 15 maja 2022 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 184 wizyt

92,460 zapytań

141,265 odpowiedzi

319,104 komentarzy

61,856 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!

...