[蓝桥杯青少年组省赛 2024] 物品分组

Luogu
IDLGB4305
Time1000ms
Memory512MB
DifficultyP2
二分2024枚举蓝桥杯青少年组
有 $n$ 件物品排成一排,编号分别为 $1, 2, \ldots, n$,价值分别为 $a_1, a_2, \ldots, a_n$。请将这 $n$ 件物品拆分为 $k$ 组(不改变物品的顺序),要求每组内至少有一件物品。分别统计每组物品的价值之和,并找出其中的最大值。请设计一种分组方案,使这个最大值尽可能小,并输出这个最大值。 例如,$n=5$,物品价值分别为 $6, 1, 3, 8, 4$;$k=2$,表示要将这 $5$ 件物品拆分为两组。有如下分组方案: 1. $(6)$ 和 $(1, 3, 8, 4)$,两组价值之和分别为 $6$ 和 $16$,最大值为 $16$; 2. $(6, 1)$ 和 $(3, 8, 4)$,两组价值之和分别为 $7$ 和 $15$,最大值为 $15$; 3. $(6, 1, 3)$ 和 $(8, 4)$,两组价值之和分别为 $10$ 和 $12$,最大值为 $12$; 4. $(6, 1, 3, 8)$ 和 $(4)$,两组价值之和分别为 $18$ 和 $4$,最大值为 $18$。 其中第 $3$ 种方案的最大值 $12$ 是所有方案中最小的,故输出 $12$。 ## Input - 第一行输入一个整数 $n$($1 \leq n \leq 1000$),表示物品的数量; - 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$($1 \leq a_i \leq 10^5$),表示各物品的价值,整数之间以空格隔开; - 第三行输入一个整数 $k$($1 \leq k \leq n$),表示分组的数量。 ## Output 输出一个整数,表示所有可能分组方案中,各组价值之和的最大值的最小可能值。 [samples]
Samples
Input #1
5
6 1 3 8 4
2
Output #1
12
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯青少年组省赛 2024] 物品分组",
    "description": {
      "content": "有 $n$ 件物品排成一排,编号分别为 $1, 2, \\ldots, n$,价值分别为 $a_1, a_2, \\ldots, a_n$。请将这 $n$ 件物品拆分为 $k$ 组(不改变物品的顺序),要求每组内至少有一件物品。分别统计每组物品的价值之和,并找出其中的最大值。请设计一种分组方案,使这个最大值尽可能小,并输出这个最大值。 例如,$n=5$,物品价值分别为 $6, 1, 3, 8, 4$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4305"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 件物品排成一排,编号分别为 $1, 2, \\ldots, n$,价值分别为 $a_1, a_2, \\ldots, a_n$。请将这 $n$ 件物品拆分为 $k$ 组(不改变物品的顺序),要求每组内至少有一件物品。分别统计每组物品的价值之和,并找出其中的最大值。请设计一种分组方案,使这个最大值尽可能小,并输出这个最大值。\n\n例如,$n=5$,物品价值分别为 $6, 1, 3, 8, 4$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments