P1094 [NOIP 2007 Junior] Souvenir Grouping

NOIP2007 普及组 T2

New Year’s Day is coming, and the student council has tasked Lele with distributing souvenirs at the New Year’s party. To keep the value of souvenirs received by participants relatively balanced, he wants to group the purchased souvenirs by price. Each group can contain at most two souvenirs, and the sum of prices in a group cannot exceed a given integer $w$. To finish the distribution as quickly as possible, Lele wants to minimize the number of groups. Your task is to write a program that finds a grouping scheme with the minimal number of groups and outputs that minimal number.

A total of $n+2$ lines: - The first line contains an integer $w$, the upper bound on the sum of prices in each group. - The second line contains an integer $n$, the total number of souvenirs. - Lines 3 to $n+2$: each line contains a positive integer $P_i$ representing the price of the corresponding souvenir.

A single integer: the minimal number of groups.

Constraints: - $50\%$ of the testdata: $1 \le n \le 15$. - $100\%$ of the testdata: $1 \le n \le 3\times 10^4$, $80 \le w \le 200$, $5 \le P_i \le w$. Translated by ChatGPT 5