zadanie bierki

Question

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;
}

 

Answer 1

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.

Comments

Kod robi mniej więcej to samo, ale jest mało czytelny przez niepotrzebną arytmetykę na wskaźnikach

Answer 2

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;
}

 

Comments

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.

---

Tak, racja