#include #include // Počet kusů a jejich délky // * kl je levý konec platné části k (index první platné položky) int n, *k, kl; // Fronta délek slepených kusů // * s levým a pravým koncem platné části int *s, sl, sp; // Výstupní buffer struct Rezani { int kus1; int kus2; }; struct Rezani *o; int op; // Běžná porovnávací funkce pro vzestupné uspořádání integerů int int_cmp(const void *A, const void *B) { int a = *(int *)A; int b = *(int *)B; if (a < b) return -1; if (a > b) return 1; return 0; } int main() { // Čtení vstupu scanf("%d", &n); if (n < 2) return 0; k = malloc(n * sizeof(*k)); kl = 0; for (int i = 0; i < n; i++) { scanf("%d", &k[i]); } // Setřídění k // * QuickSort může běžet v čase až O(n^2), předpokládáme průměrný případ O(n log n) // * Kdybychom potřebovali rychlost zaručenou, využijeme třeba merge sort. qsort(k, n, sizeof(*k), int_cmp); // Inicializace fronty lepených kusů s a výstupního zásobníku o // * Velikosti se dají snadno spočítat z toho, že řezů/lepení je n-1. s = malloc((n-1) * sizeof(*s)); sl = 0; sp = -1; o = malloc((n-1) * sizeof(*o)); op = -1; // Výpočet int a, b; o[++op] = (struct Rezani){k[kl], k[kl+1]}; s[++sp] = k[kl] + k[kl+1]; kl += 2; for (int i = 0; i < n - 2; i++) { // Výběr nejmenších dvou kusů, které jsou aktuálně k dispozici if (kl < n) { // Fronta k není prázdná, musíme počítat minimum... if (k[kl] <= s[sl]) { a = k[kl++]; } else { a = s[sl++]; } // ... a minimum ze zbytku. if (kl < n && k[kl] <= s[sl]) { b = k[kl++]; } else { b = s[sl++]; } } else { a = s[sl++]; b = s[sl++]; } // Uložení informace o řezu a lepení o[++op] = (struct Rezani){a, b}; s[++sp] = a + b; } // Vygenerování výstupu while (op >= 0) { printf( "%d -> %d + %d\n", o[op].kus1 + o[op].kus2, o[op].kus1, o[op].kus2 ); op--; } // O dealokaci paměti se po skončení programu postará systém. return 0; }