磨坊里有 n 根年糕条，每根的长度以整数给出。
主人打算切 k 次。
每切一次，都从现有的年糕条中选出最长的一根，分成两段。
如果最长的有好几根，选其中哪一根都可以。
长度为 x 的年糕条会分成一段长度为 x 除以 2 的商的，和一段长度为剩下部分的。
所以 x 是偶数时两段一样长，是奇数时其中一段长 1。
两段都放回年糕堆里，下次切的时候和其他年糕条一样比较长度。
如果最长的年糕条长度是 1，就不能再切了，即使还有剩余次数也在那里停下。
每切一次，在一行里输出分出的两段的长度，短的在前，用一个空格隔开。
最后一行输出全部结束时年糕条的根数和最长一根的长度，用一个空格隔开。
3 4 7 4 1
3 4 2 2 2 2 1 2 7 2
2 5 2 1
1 1 3 1
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
反复做“取出最长的，再把新的值放回去”这件事，合适的工具是堆（优先队列）。
可是先出来的是哪一头，各语言不一样。
陷阱一：Python heapq、Java PriorityQueue、C# PriorityQueue<值, 优先级> 都是最小的先出来。
照原样用就会取出最短的年糕条：示例 1 中看到长度 1 就立刻停下，只输出 3 1 一行，示例 2 变成 2 1。
Python 放入 -x，取出时再把符号翻回来；Java 写 new PriorityQueue<>(Collections.reverseOrder())；C# 写 Enqueue(x, -x)。
只有 C++ priority_queue<int> 是最大的先出来，照原样用就行。
JS、TS、C 和 Craykon 没有堆，要用数组自己做：父节点在 (i - 1) / 2 号，两个子节点在 2 * i + 1 号和 2 * i + 2 号。
陷阱二：C++ 的 top() 只是看，pop() 不返回值。
漏掉 pop() 的话，切过的年糕条还留在堆里，示例 1 会输出四次 3 4，最后以 11 7 结束。
Python heappop、Java poll、C# Dequeue 都是取出的同时返回值。
陷阱三：如果两段都用 x / 2，长度是奇数时整数除法丢掉的那个 1 就从年糕上消失了。
示例 1 的第一行变成 3 3。
长的一段要用 x - 商 来求。
JS、TS 和 Craykon 的 / 正相反，会得出小数，输出 3.5 3.5，所以要写 Math.floor(x / 2)、数学.商(x, 2)，Python 用 //。
陷阱四：如果不问最长的年糕条是不是 1，就会把长度 1 的切成 0 和 1。
示例 2 在 1 1 之后输出四次 0 1，最后以 7 1 结束。
这道题里年糕条最多 2,000 根，所以每次都在整个列表里找最大值也能在时间内完成。
堆把这一步从“有几根比几次”降到这个规模下的二十来次比较。
实际测量，年糕条和次数各为 200,000 时，用 C 每次扫一遍整个列表要花几十秒以上，而堆在 0.1 秒内完成。
import sysimport heapq data = sys.stdin.read().split()n, k = int(data[0]), int(data[1])# heapq는 가장 작은 값이 먼저 나온다. 가장 긴 떡이 먼저 나오도록 부호를 뒤집어 넣는다heap = [-int(x) for x in data[2:2 + n]]heapq.heapify(heap) out = []for _ in range(k): if -heap[0] == 1: # 가장 긴 떡이 1이면 더 썰 수 없다 break x = -heapq.heappop(heap) # 가장 긴 떡을 꺼낸다 a = x // 2 # 짧은 도막 b = x - a # 긴 도막: x가 홀수면 1만큼 더 길다 out.append(f"{a} {b}") heapq.heappush(heap, -a) heapq.heappush(heap, -b)out.append(f"{len(heap)} {-heap[0]}")print("\n".join(out))const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);const n = data[0];const k = data[1]; // JS에는 힙이 없어서 배열로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다const heap = []; function push(v) { heap.push(v); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }} function pop() { const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; let i = 0; while (true) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[i], heap[big]] = [heap[big], heap[i]]; i = big; } } return top;} for (let i = 0; i < n; i++) push(data[2 + i]); const out = [];for (let i = 0; i < k; i++) { if (heap[0] === 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 const x = pop(); // 가장 긴 떡을 꺼낸다 const a = Math.floor(x / 2); // 짧은 도막. JS의 /는 3.5 같은 소수를 내므로 내림한다 const b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.push(`${a} ${b}`); push(a); push(b);}out.push(`${heap.length} ${heap[0]}`);console.log(out.join("\n"));import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((s: string): boolean => s !== "").map(Number);const n: number = data[0];const k: number = data[1]; // TS에도 힙이 없어서 배열로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다const heap: number[] = []; function push(v: number): void { heap.push(v); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }} function pop(): number { const top: number = heap[0]; const last = heap.pop() as number; if (heap.length > 0) { heap[0] = last; let i = 0; while (true) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[i], heap[big]] = [heap[big], heap[i]]; i = big; } } return top;} for (let i = 0; i < n; i++) push(data[2 + i]); const out: string[] = [];for (let i = 0; i < k; i++) { if (heap[0] === 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 const x: number = pop(); // 가장 긴 떡을 꺼낸다 const a: number = Math.floor(x / 2); // 짧은 도막. /는 3.5 같은 소수를 내므로 내림한다 const b: number = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.push(`${a} ${b}`); push(a); push(b);}out.push(`${heap.length} ${heap[0]}`);console.log(out.join("\n"));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Collections;import java.util.PriorityQueue;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); // PriorityQueue는 가장 작은 값이 먼저 나온다. reverseOrder()를 넘겨 가장 긴 떡이 먼저 나오게 한다 PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { heap.add(Integer.parseInt(st.nextToken())); } StringBuilder out = new StringBuilder(); for (int i = 0; i < k; i++) { if (heap.peek() == 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 int x = heap.poll(); // 가장 긴 떡을 꺼낸다 int a = x / 2; // 짧은 도막 int b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.append(a).append(' ').append(b).append('\n'); heap.add(a); heap.add(b); } out.append(heap.size()).append(' ').append(heap.peek()); System.out.println(out); }}using System;using System.Collections.Generic;using System.Text; class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int n = int.Parse(first[0]); int k = int.Parse(first[1]); string[] parts = Console.ReadLine().Trim().Split(' '); // PriorityQueue<값, 우선순위>는 우선순위가 가장 작은 것이 먼저 나온다. // 우선순위를 -길이로 주어 가장 긴 떡이 먼저 나오게 한다 var heap = new PriorityQueue<int, int>(); for (int i = 0; i < n; i++) { int len = int.Parse(parts[i]); heap.Enqueue(len, -len); } var sb = new StringBuilder(); for (int i = 0; i < k; i++) { if (heap.Peek() == 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 int x = heap.Dequeue(); // 가장 긴 떡을 꺼낸다 int a = x / 2; // 짧은 도막 int b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 sb.Append(a).Append(' ').Append(b).Append('\n'); heap.Enqueue(a, -a); heap.Enqueue(b, -b); } sb.Append(heap.Count).Append(' ').Append(heap.Peek()); Console.WriteLine(sb); }}#include <iostream>#include <queue>using namespace std; int main() { int n, k; cin >> n >> k; // priority_queue는 다른 언어와 달리 가장 큰 값이 먼저 나온다. 그대로 쓰면 된다 priority_queue<int> heap; for (int i = 0; i < n; i++) { int len; cin >> len; heap.push(len); } for (int i = 0; i < k; i++) { if (heap.top() == 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 int x = heap.top(); // top()은 보기만 한다 heap.pop(); // 꺼내는 것은 pop()이고, 값을 돌려주지 않는다 int a = x / 2; // 짧은 도막 int b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 cout << a << ' ' << b << '\n'; heap.push(a); heap.push(b); } cout << heap.size() << ' ' << heap.top() << '\n'; return 0;}#include <stdio.h> /* C에는 힙이 없어서 배열로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다 */static int heap[2000]; /* 처음 1,000개 + 썰 때마다 하나씩 늘어 1,000개 */static int size = 0; static void push(int v) { int i = size++; heap[i] = v; while (i > 0) { int parent = (i - 1) / 2; if (heap[parent] >= heap[i]) break; int t = heap[i]; heap[i] = heap[parent]; heap[parent] = t; i = parent; }} static int pop(void) { int top = heap[0]; heap[0] = heap[--size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, big = i; if (l < size && heap[l] > heap[big]) big = l; if (r < size && heap[r] > heap[big]) big = r; if (big == i) break; int t = heap[i]; heap[i] = heap[big]; heap[big] = t; i = big; } return top;} int main(void) { int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { int len; scanf("%d", &len); push(len); } for (int i = 0; i < k; i++) { if (heap[0] == 1) break; /* 가장 긴 떡이 1이면 더 썰 수 없다 */ int x = pop(); /* 가장 긴 떡을 꺼낸다 */ int a = x / 2; /* 짧은 도막 */ int b = x - a; /* 긴 도막: x가 홀수면 1만큼 더 길다 */ printf("%d %d\n", a, b); push(a); push(b); } printf("%d %d\n", size, heap[0]); return 0;}// 크레이콘에는 힙이 없어서 목록으로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다첫줄 = 控制台.读数字();n = 첫줄[0];k = 첫줄[1];길이들 = 控制台.读数字();heap = []; 힙넣기(v){ heap.添加(v); i = heap.数量 - 1; 当 (i > 0) { 부모 = 数学.商(i - 1, 2); 如果 (heap[부모] >= heap[i]) { 跳出; } t = heap[i]; heap[i] = heap[부모]; heap[부모] = t; i = 부모; }} 힙빼기(){ top = heap[0]; heap[0] = heap[heap.数量 - 1]; heap.按位置移除(heap.数量 - 1); i = 0; 当 (真) { l = 2 * i + 1; r = l + 1; big = i; 如果 (l < heap.数量 && heap[l] > heap[big]) { big = l; } 如果 (r < heap.数量 && heap[r] > heap[big]) { big = r; } 如果 (big == i) { 跳出; } t = heap[i]; heap[i] = heap[big]; heap[big] = t; i = big; } 返回 top;} 遍历 (len 在 길이들){ 힙넣기(len);} out = [];循环 (i = 0; i < k; i++){ 如果 (heap[0] == 1) { 跳出; } x = 힙빼기(); // 가장 긴 떡을 꺼낸다 a = 数学.商(x, 2); // 짧은 도막. /는 3.5 같은 소수를 내므로 몫을 구한다 b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.添加(a + " " + b); 힙넣기(a); 힙넣기(b);}out.添加(heap.数量 + " " + heap[0]);控制台.输出(out.连接("\n"));