算法设计与分析 Lab10

# Description

There are N lab classes. The i-th class has $A_i$ students now. The i-th class can contain no more than $B_i$ students. Hong thinks that the number of classes is too large. She wants to reassign the students into minimal number of classes. However, Hong wants to reassign the minimal number of students.

Hong wants you to calculate the minimal number of students to reassign.

# Input

The first line contains a integer $N$.

Each of the next N line contains two integers, $A_i$ and $B_i$ ​ .

# Output

Output one integer, shows the minimal number of students to reassign.

# Sample Input

2
1 2
1 2

# Sample output

1

# Limit

1 second for each test case. The memory limit is 256MB.

For 60% test cases, the data is generated by random.

For 100% test cases, $1 \leq N \leq 100$, $1 \leq A_i \leq B_i \leq 100$.

# Solution

设有一个集合 $S$，我们只保留标号为$i \in S$的教室关闭，剩余的教室开设。

那么这个集合 $S$ 应该满足：

$\sum_{n=1}^N a[i] \leq \sum_{i \notin S} b[i]$

两边同时加上 $\sum_{i \in S} b[i]$

$\sum_{n=1}^N a[i] + \sum_{i \in S} b[i] \leq \sum_{i \notin S} b[i] + \sum_{i \in S} b[i]$

$\sum_{n=1}^N a[i] + \sum_{i \in S} b[i] \leq \sum_{n=1}^N b[i]$

$\sum_{i \in S} b[i] \leq \sum_{n=1}^N (b[i] - a[i]) = \text{constant}$

现在，我们可以把 $b[i]$ 当做物品重量，所有物品的价值都是1，背包的容量为 $\sum_{n=1}^N (b[i] - a[i])$，做01背包装入尽量多的物品，相当于关掉尽量多的房间。

对于最少移动人数的问题，首先要注意到这个最少移动人数的前提是已经关掉了最多的房间，或者说答案要求的是在不考虑移动人数的情况下开启教室数最少的方案中移动人数最少的是多少；另外最少移动人数也可以通过之前的状态进行递推，比如你选择关掉第3个房间，那么关掉3个房间最少移动人数，应该是关掉2个房间的最少移动人数加上第3个房间的人数。如果两种方案关掉房间数不同，答案应直接用关闭房间数更多的移动人数更新；否则，答案取两种方案中移动人数更少的人数。

# Code

30行不到 不敢发qwq