快递箱按到达顺序装上卡车。 一辆卡车可以一直装到总重量达到 C 为止。 每个箱子有运单号、目的地和重量。 箱子到达时，按以下规则选择卡车。 - 在还没出发的卡车中，找目的地与这个箱子相同、装上这个箱子后总重量仍不超过 C 的卡车。 - 这样的卡车有多辆时，装上编号最小的那辆。 不是剩余空间最大或最小的那辆。 - 没有这样的卡车时，叫一辆新卡车来装。 卡车按被叫来的顺序编号 1, 2, 3, …，新卡车的目的地就是这个箱子的目的地。 - 装上箱子后，如果那辆卡车的总重量恰好等于 C，卡车立即出发。 出发的卡车不再装货。 所有箱子装完后，还没出发的卡车按编号顺序出发。 第一行给出 C 和箱子数 n，接下来 n 行按到达顺序给出"运单号 目的地 重量"，用一个空格隔开。 第一行输出卡车数。 接着按出发顺序，每辆卡车输出一行："编号 目的地 总重量 箱子数"，后面是这辆车按装车顺序装的运单号，全部用一个空格隔开。 试着把一个箱子和一辆卡车分别打包成记录（结构体），并处理卡车记录的列表。
输入
1 ≤ n ≤ 1,000，1 ≤ C ≤ 1,000,000，1 ≤ 重量 ≤ C（整数）。 运单号由 1～8 个英文大写字母和数字组成，互不相同。 目的地是 1～10 个英文小写字母。
输出
一行卡车数，接着每辆卡车一行
样例 1 · stdin
10 7
P1 seoul 6
P2 busan 4
P3 seoul 5
P4 busan 6
P5 seoul 4
P6 seoul 3
P7 seoul 5
stdout
4
2 busan 10 2 P2 P4
1 seoul 10 2 P1 P5
3 seoul 8 2 P3 P6
4 seoul 5 1 P7
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
打包一辆卡车（编号、目的地、总重量、运单列表）的方法：Python @dataclass（列表字段要用 field(default_factory=list)），Java 用字段可改的 class（record 的字段不能改），C# class，C、C++ struct，JS、TS 对象 { no, dest, load, codes: [] }（TS 用 interface Truck 写出形状）。 Craykon 没有类，所以每辆卡车做一个 字典()（t["load"]、t["codes"]），用 waiting.添加(t) 放进列表。 关键在于修改选中的卡车。 Python、JS、TS、Java、C# 的 class、Craykon 的字典里，从列表取出的值指向同一辆卡车，所以 truck.load += w 会改到列表里的卡车。 C 要像 Truck *t = &trucks[k] 这样用指针，C++ 要像 Truck &t = trucks[k] 这样用引用来拿；C++ 的 vector 变大时会搬动元素，手里的引用会失效，所以要先 reserve，或者按下标重新找。 出发的卡车要从等待列表中移除：Python remove，JS、TS splice，Java、C# Remove，Craykon 按位置移除。 五个陷阱：① 写成 load + w < C 就选不到恰好装到 C 的卡车，会去叫新车。 ② Python 里像 def __init__(self, no, dest, codes=[]) 这样把默认值设成 []，所有卡车会共用这一个列表，运单号就混在一起（@dataclass 直接拒绝这种默认值）。 ③ C# 里把卡车写成 struct，Truck truck = waiting[at]; 是副本，改了 Load 列表里也不变（C 的 Truck t = trucks[k]; 也一样）。 ④ 按卡车编号顺序输出是错的：装满先出发的卡车在前。 ⑤ 只看目的地相同的最后一辆卡车（next-fit），会漏掉前面卡车剩下的空间。
Pythonmain.py · 38 行
import sysfrom dataclasses import dataclass, field@dataclassclass Truck: no: int dest: str load: int = 0 codes: list[str] = field(default_factory=list) # 트럭마다 새 목록def main(): data = sys.stdin.read().split() cap, n = int(data[0]), int(data[1]) trucks = 0 waiting: list[Truck] = [] # 아직 떠나지 않은 트럭(번호 순) departed: list[Truck] = [] # 떠난 차례 for i in range(n): code, dest, w = data[2 + 3 * i], data[3 + 3 * i], int(data[4 + 3 * i]) truck = next((t for t in waiting if t.dest == dest and t.load + w <= cap), None) if truck is None: trucks += 1 truck = Truck(trucks, dest) waiting.append(truck) truck.load += w truck.codes.append(code) if truck.load == cap: # 꽉 차면 곧바로 떠난다 waiting.remove(truck) departed.append(truck) departed.extend(waiting) # 남은 트럭은 번호 순으로 out = [str(len(departed))] for t in departed: out.append(f"{t.no} {t.dest} {t.load} {len(t.codes)} " + " ".join(t.codes)) print("\n".join(out))main()
JavaScriptmain.js · 27 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const cap = Number(data[0]);const n = Number(data[1]);let count = 0;const waiting = []; // 아직 떠나지 않은 트럭(번호 순)const departed = []; // 떠난 차례for (let i = 0; i < n; i++) { const code = data[2 + 3 * i]; const dest = data[3 + 3 * i]; const w = Number(data[4 + 3 * i]); let truck = waiting.find((t) => t.dest === dest && t.load + w <= cap); if (truck === undefined) { count++; truck = { no: count, dest, load: 0, codes: [] }; // 트럭마다 새 객체·새 배열 waiting.push(truck); } truck.load += w; truck.codes.push(code); if (truck.load === cap) { waiting.splice(waiting.indexOf(truck), 1); departed.push(truck); }}departed.push(...waiting);const out = [String(departed.length)];for (const t of departed) out.push(`${t.no} ${t.dest} ${t.load} ${t.codes.length} ${t.codes.join(" ")}`);console.log(out.join("\n"));
TypeScriptmain.ts · 34 行
interface Truck { no: number; dest: string; load: number; codes: string[];}const data: string[] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const cap = Number(data[0]);const n = Number(data[1]);let count = 0;const waiting: Truck[] = []; // 아직 떠나지 않은 트럭(번호 순)const departed: Truck[] = []; // 떠난 차례for (let i = 0; i < n; i++) { const code = data[2 + 3 * i]; const dest = data[3 + 3 * i]; const w = Number(data[4 + 3 * i]); let truck: Truck | undefined = waiting.find((t) => t.dest === dest && t.load + w <= cap); if (truck === undefined) { count++; truck = { no: count, dest, load: 0, codes: [] }; waiting.push(truck); } truck.load += w; truck.codes.push(code); if (truck.load === cap) { waiting.splice(waiting.indexOf(truck), 1); departed.push(truck); }}departed.push(...waiting);const out: string[] = [String(departed.length)];for (const t of departed) out.push(`${t.no} ${t.dest} ${t.load} ${t.codes.length} ${t.codes.join(" ")}`);console.log(out.join("\n"));
JavaMain.java · 59 行
import java.io.*;import java.util.*;public class Main { // 트럭 하나: 실은 상자가 늘어나니 record가 아니라 필드를 바꿀 수 있는 클래스 static class Truck { final int no; final String dest; int load = 0; final List<String> codes = new ArrayList<>(); Truck(int no, String dest) { this.no = no; this.dest = dest; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int cap = Integer.parseInt(st.nextToken()); int n = Integer.parseInt(st.nextToken()); int count = 0; List<Truck> waiting = new ArrayList<>(); List<Truck> departed = new ArrayList<>(); for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); String code = st.nextToken(); String dest = st.nextToken(); int w = Integer.parseInt(st.nextToken()); Truck truck = null; for (Truck t : waiting) { if (t.dest.equals(dest) && t.load + w <= cap) { truck = t; break; } } if (truck == null) { truck = new Truck(++count, dest); waiting.add(truck); } truck.load += w; truck.codes.add(code); if (truck.load == cap) { waiting.remove(truck); departed.add(truck); } } departed.addAll(waiting); StringBuilder sb = new StringBuilder(); sb.append(departed.size()).append('\n'); for (Truck t : departed) { sb.append(t.no).append(' ').append(t.dest).append(' ').append(t.load).append(' ').append(t.codes.size()); for (String c : t.codes) sb.append(' ').append(c); sb.append('\n'); } System.out.print(sb); }}
C#Main.cs · 56 行
using System;using System.Collections.Generic;using System.Text;// class라서 목록에서 꺼낸 t는 같은 트럭을 가리킨다(struct였다면 복사본)class Truck{ public int No; public string Dest; public int Load; public List<string> Codes = new List<string>(); public Truck(int no, string dest) { No = no; Dest = dest; }}class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int cap = int.Parse(data[0]); int n = int.Parse(data[1]); int count = 0; var waiting = new List<Truck>(); var departed = new List<Truck>(); for (int i = 0; i < n; i++) { string code = data[2 + 3 * i]; string dest = data[3 + 3 * i]; int w = int.Parse(data[4 + 3 * i]); Truck truck = waiting.Find(t => t.Dest == dest && t.Load + w <= cap); if (truck == null) { truck = new Truck(++count, dest); waiting.Add(truck); } truck.Load += w; truck.Codes.Add(code); if (truck.Load == cap) { waiting.Remove(truck); departed.Add(truck); } } departed.AddRange(waiting); var sb = new StringBuilder(); sb.Append(departed.Count).Append('\n'); foreach (var t in departed) sb.Append($"{t.No} {t.Dest} {t.Load} {t.Codes.Count} {string.Join(" ", t.Codes)}\n"); Console.Write(sb); }}
C++main.cpp · 57 行
#include <iostream>#include <string>#include <vector>struct Truck { int no; std::string dest; int load = 0; std::vector<std::string> codes;};int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int cap, n; std::cin >> cap >> n; std::vector<Truck> trucks; trucks.reserve(n); // 상자마다 많아야 한 대: 자리를 미리 잡아 옮겨지지 않게 std::vector<int> waiting; // 아직 떠나지 않은 트럭의 자리(번호 순) std::vector<int> departed; // 떠난 차례 for (int i = 0; i < n; i++) { std::string code, dest; int w; std::cin >> code >> dest >> w; int pick = -1, at = -1; for (int k = 0; k < (int)waiting.size(); k++) { const Truck &t = trucks[waiting[k]]; if (t.dest == dest && t.load + w <= cap) { pick = waiting[k]; at = k; break; } } if (pick < 0) { trucks.push_back(Truck{(int)trucks.size() + 1, dest}); pick = (int)trucks.size() - 1; waiting.push_back(pick); at = (int)waiting.size() - 1; } Truck &t = trucks[pick]; // 참조라서 목록 안의 트럭이 바뀐다 t.load += w; t.codes.push_back(code); if (t.load == cap) { waiting.erase(waiting.begin() + at); departed.push_back(pick); } } departed.insert(departed.end(), waiting.begin(), waiting.end()); std::cout << departed.size() << '\n'; for (int k : departed) { const Truck &t = trucks[k]; std::cout << t.no << ' ' << t.dest << ' ' << t.load << ' ' << t.codes.size(); for (const auto &c : t.codes) std::cout << ' ' << c; std::cout << '\n'; } return 0;}
Cmain.c · 69 行
#include <stdio.h>#include <string.h>#define MAXN 1000typedef struct { char code[9]; char dest[11]; int w; int next; /* 같은 트럭에 다음으로 실린 상자(없으면 -1) */} Parcel;typedef struct { int no; char dest[11]; int load; int count; int first, last; /* 실은 상자들의 첫·마지막 번호 */ int gone; /* 떠났으면 1 */} Truck;static Parcel parcels[MAXN];static Truck trucks[MAXN]; /* 상자마다 많아야 한 대 새로 생긴다 */static int order[MAXN]; /* 떠난 차례 */int main(void) { int cap, n, nt = 0, nd = 0; scanf("%d %d", &cap, &n); for (int i = 0; i < n; i++) { Parcel *p = &parcels[i]; scanf("%8s %10s %d", p->code, p->dest, &p->w); p->next = -1; Truck *t = NULL; /* 고른 트럭을 포인터로 쥐어야 목록 안의 트럭이 바뀐다 */ for (int k = 0; k < nt; k++) { if (!trucks[k].gone && strcmp(trucks[k].dest, p->dest) == 0 && trucks[k].load + p->w <= cap) { t = &trucks[k]; break; } } if (t == NULL) { t = &trucks[nt]; t->no = ++nt; strcpy(t->dest, p->dest); t->load = 0; t->count = 0; t->first = -1; t->gone = 0; } t->load += p->w; t->count++; if (t->first < 0) t->first = i; else parcels[t->last].next = i; t->last = i; if (t->load == cap) { t->gone = 1; order[nd++] = t->no - 1; } } for (int k = 0; k < nt; k++) if (!trucks[k].gone) order[nd++] = k; printf("%d\n", nd); for (int j = 0; j < nd; j++) { const Truck *t = &trucks[order[j]]; printf("%d %s %d %d", t->no, t->dest, t->load, t->count); for (int i = t->first; i >= 0; i = parcels[i].next) printf(" %s", parcels[i].code); printf("\n"); } return 0;}
Craykonmain.cray · 51 行
// 크레이콘에는 클래스가 없어서 트럭 한 대를 사전 하나로 묶는다(no, dest, load, codes)첫줄 = 控制台.读数字();cap = 첫줄[0];n = 첫줄[1];count = 0;waiting = []; // 아직 떠나지 않은 트럭(번호 순)departed = []; // 떠난 차례循环 (i = 0; i < n; i++){ p = 控制台.读行().去空白().分割(" "); code = p[0]; dest = p[1]; w = p[2].转数字(); at = -1; 循环 (k = 0; k < waiting.数量; k++) { 如果 (waiting[k]["dest"] == dest && waiting[k]["load"] + w <= cap) { at = k; 跳出; } } 如果 (at < 0) { count++; t = 字典(); // 트럭마다 새 사전, 새 목록 t["no"] = count; t["dest"] = dest; t["load"] = 0; t["codes"] = []; waiting.添加(t); at = waiting.数量 - 1; } truck = waiting[at]; // 같은 사전을 가리킨다: 고치면 목록 안의 트럭이 바뀐다 truck["load"] = truck["load"] + w; truck["codes"].添加(code); 如果 (truck["load"] == cap) { waiting.按位置移除(at); departed.添加(truck); }}遍历 (t 在 waiting){ departed.添加(t);}控制台.输出(departed.数量);遍历 (t 在 departed){ 控制台.输出(t["no"] + " " + t["dest"] + " " + t["load"] + " " + t["codes"].数量 + " " + t["codes"].连接(" "));}