BYR Achieve · 镜像论坛

# 垃圾优先 Time Limit: 10ms Memory Limit: 2GiB ## Description 爪哇岛的住民很喜欢购买和使用一次性用品，因此，爪哇岛的垃圾回收是一个大问题。这对爪哇旅馆的运营产生了很大的影响。每天，爪哇旅馆每个客房的客人都会产生很多垃圾。多到什么程度呢？多到旅馆宁可给客人们开新的房间，让清洁工们把客人有用的东西搬到新房间里（别问我清洁工怎么知道哪些东西有用的，他们很聪明），然后把旧房间里剩下的破烂儿全都清扫走。爪哇旅馆有很多清洁工，每天都要帮客人们尽快清理垃圾。但是，客人晚上需要在客房中休息，不可以打扰，因此，垃圾回收的工作只能在白天客人外出的时候进行。由于时间有限，一天不一定能够把所有的客房都清理完。因此，清洁工采用旅馆的“垃圾优先”政策：在一天中，尽可能清理最多的房间，剩下的房间来不及打扰的就明天再清理。不用担心有的房间没清理，因为清洁工的清理方法是把有用的东西搬出来，剩下的扔掉。随着客人入住的时间越来越长，客人们有用的东西会慢慢变少，早晚全都会变成垃圾，将来清理房间用的时间将越来越短。这就是为什么这种政策叫“垃圾优先”：优先清理的房间一般是垃圾最多的房间。不过这都是细节。我们要做的，仅仅是为清洁工们安排一天的工作内容。已知旅馆一共有`N`个房间有客人，清理每个房间所需的时间分别是`G[1], G[2], ..., G[N]`。一共`M`名清洁工，工作效率一样。白天留给清洁工们清扫的总时间是`T`。不同清洁工可以同时工作，但每个房间同时只能有一个清洁工清洁。每个房间可以清理，也可以不清理，但不能清理一半。而每个清洁工也都必须清理完一个房间才能清理另一个。而你要做的就是决定哪个清洁工清理哪些房间，使得`T`时间内可以清理尽可能多的房间。 # Input 输入包含两行。第一行有三个整数：`N`、`M`、`T`，以一个空格隔开。第二行有`N`个整数，分别是`G[1] ... G[N]`，以一个空格隔开。数据范围就不指定了，反正我这里也没有标准答案。想时间复杂度尽可能小的算法吧。 # Output 输出一个整数，就是最多可以清理的房间的数量 # Sample Input ``` 10 4 10 1 2 3 4 5 6 7 8 9 10 ``` # Sample Output ``` 8 ``` # 说明 Sample Input有4个清洁工，时间是10。让4个人清理的房间分别是1+9, 2+8, 3+7, 4+6，这样每个人都花10的时间，一共可以清理8个房间。

【思考题】垃圾优先