Piramida – Omówienie zadania – Kolejka monotoniczna

Szczegółowe omówienie zadania Piramida:

Link do powyższego omówienia zadania Piramida: https://youtu.be/JJzOAD4SBpc?t=1243
Omówienie kodu zadania Piramida: https://youtu.be/JJzOAD4SBpc?t=4324
Link do treści zadania Piramida i możliwości umieszczania rozwiązań: https://szkopul.edu.pl/problemset/problem/0qINw7rrL7Bz0W90zn2L5BiV/site/

Zadanie Piramida to zadanie na pomysł / kolejkę monotoniczną: https://youtu.be/JJzOAD4SBpc?t=2155
W naszym zadaniu zaimplementowana jako stos, który pamięta sumę: https://youtu.be/JJzOAD4SBpc?t=3127
Symulacja algorytmu: https://youtu.be/JJzOAD4SBpc?t=3246
Pseudokod: https://youtu.be/JJzOAD4SBpc?t=3896
Złożoność rozwiązania: https://youtu.be/JJzOAD4SBpc?t=4000

To zadanie wymaga po prostu narysowania / symulacji / obrócenia kartki: https://youtu.be/JJzOAD4SBpc?t=6443
Co prowadzi do prostego pomysłu: https://youtu.be/JJzOAD4SBpc?t=1790


Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109


Kod C++ programu "Piramida", który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 7;

int t[MAXN];

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

	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> t[i];

	stack<pair<int, int>> stos;
	stos.push({1000001, 0});
	long long suma = 0;
	long long wynik = 0;
	for (int i = 1; i <= n; ++i) {
		int ile = 1;
		while (stos.top().first < t[i]) {
			ile += stos.top().second;
			suma -= (long long)stos.top().second*stos.top().first;
			stos.pop();
		}
		suma += (long long)ile*t[i];
		wynik += suma;
		stos.push({t[i], ile});
	}
	cout << wynik << '\n';
	return 0;
}
Kod C++ programu "Piramida", który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Kod Python programu Piramida, który otrzymuje 100%:

def solve():
	n = int(input())
	t = map(int, input().split())

	stos = [[1000001, 0]]
	suma = 0
	wynik = 0
	for wart in t:
		ile = 1
		while (stos[-1][0] < wart):
			ile += stos[-1][1]
			suma -= stos[-1][1]*stos[-1][0]
			stos.pop()
		suma += wart*ile
		wynik += suma
		stos.append([wart, ile])

	print(wynik)

solve()

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz