题目：

小 P 计划招募 n 个机器人完成一个项目：每个机器人负责其中的一项任务，编号从 1 到 n，任务之间互不干扰。如果完成任务 i 的耗时为 ti​，则该项目总耗时为 t1+t2+⋯+tn。

作为项目管理者，小 P 可以用有限的预算为机器人们购买咖啡加油。其中负责任务 i 的机器人，最多可以喝 ai 杯咖啡，从而将该任务耗时缩短 bi​（最终耗时即为 ti−bi​）。

根据任务的特性和机器人的偏好，n 项任务可分为“灵活型”和“普通型”两类。

灵活型：如果任务 i 是灵活型，则可以提供给该任务 [0,ai​] 范围内的任意实数杯咖啡，从而将其加速相应比例。

若给任务 i 提供 ki​⋅ai​ 杯咖啡，则该任务对应耗时 ti​−ki​⋅bi​ (0≤ki​≤1)。

普通型：只能提供给任务 0 或 ai​ 杯咖啡。

换言之，只有将耗时缩短 bi 和不加速两种选择，而不能提供半杯咖啡。

已知小 P 可以为机器人们提供最多 m 杯咖啡，试计算完成整个项目的最短时间。

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 n 和 m，分别表示任务数量和咖啡数量。

接下来 n 行，每行包含空格分隔的四个整数 oi,ti,ai,bi​，表示一个任务。其中 oi∈{0,1} 表示任务类别，oi​=0 表示灵活型、oi​=1 表示普通型；其余变量含义如上所述，输入数据保证 ti​>bi​，即缩短后的耗时仍大于零。

输出格式

输出到标准输出。

输出一个实数，表示完成整个项目的最短时间。

我的第一版代码：

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    
    static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    static class Task {
        int o, t, a, b;
        double rate; // 每杯咖啡节省的时间
        Task(int o, int t, int a, int b) {
            this.o = o;
            this.t = t;
            this.a = a;
            this.b = b;
            rate = (double) b / a;
        }
    }

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int m = nextInt();
        
        List<Task> tasks = new ArrayList<>();//用于存储所有任务
        long baseTime = 0;//基础时间
        
        for (int i = 0; i < n; i++) {
            int o = nextInt();
            int t = nextInt();
            int a = nextInt();
            int b = nextInt();
            tasks.add(new Task(o, t, a, b));
            baseTime += t;
        }
        
        // 按单位咖啡节省时间降序排序
        tasks.sort((x, y) -> Double.compare(y.rate, x.rate));
        
        double coffee = m;//剩余咖啡量
        double saved = 0.0;//节约的时间
        
        for (int i = 0; i < tasks.size(); i++) {
            Task task = tasks.get(i);
            if (coffee <= 0) break;
            
            if (task.o == 0) { // 灵活型
                double use = Math.min(task.a, coffee);
                saved += use * task.rate;
                coffee -= use;
            } else { // 普通型
                if (coffee >= task.a) {
                    saved += task.b;
                    coffee -= task.a;
                }
            }
        }
        
        double ans = baseTime - saved;
        System.out.printf("%.6f\n", ans);
    }
}

第一版代码主要通过贪心算法，单位代价收益排序 + 线性选择模式来解题。其中贪心体现在使用 double rate来比较每个机器人喝了咖啡后的工作时间减少程度，使每杯咖啡的效率短期最大化，使用rate降序排序，从而永远优先处理性价比最高的任务达到局部最优。

这一版代码忽略了灵活型任务是可分割的，而普通型任务是整包的，两类任务混合时，会互相影响，导致我的样例运行一直有几个过不了，并且面临超时问题。

我的最终代码：

import java.io.*;

public class Main {

    static BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));

    static StreamTokenizer st =
            new StreamTokenizer(br);

    static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    //灵活型任务的咖啡消耗和节省时间集合
    static int[] a = new int[205];
    static int[] b = new int[205];
    static int cnt = 0;//灵活型任务数量
    
    //用于灵活型任务排序的方法
    static void sort() {

        for (int i = 1; i < cnt; i++) {

            int ta = a[i];
            int tb = b[i];

            int j = i - 1;

            //比较当前任务收益和前一个人物的收益
            while (j >= 0 && (long) tb * a[j] > (long) b[j] * ta) {

                a[j + 1] = a[j];
                b[j + 1] = b[j];

                j--;
            }

            a[j + 1] = ta;
            b[j + 1] = tb;
        }
    }

    public static void main(String[] args) throws Exception {

        int n = nextInt();
        int m = nextInt();

        long base = 0;

        int[] dp = new int[m + 1];

        for (int i = 1; i <= m; i++) {
            dp[i] = -1000000000;//当前状态不可达
        }

        int maxUsed = 0;//普通型任务最多用的咖啡数

        for (int i = 0; i < n; i++) {

            int o = nextInt();
            int t = nextInt();
            int ai = nextInt();
            int bi = nextInt();

            base += t;
     
            //把灵活型任务先存进数组
            if (o == 0) {

                a[cnt] = ai;
                b[cnt] = bi;
                cnt++;

            } else {

                int upper = Math.min(m, maxUsed + ai);//当前任务最多用的咖啡数（不能超过m）

                for (int j = upper; j >= ai; j--) {

                    int nv = dp[j - ai] + bi;

                    if (nv > dp[j]) {
                        dp[j] = nv;
                    }
                }

                maxUsed = upper;
            }
        }

        sort();//对剩下的灵活型进行倒叙排序

        double[] flex = new double[m + 1];//存储不同咖啡量下灵活型任务的最大节省时间

        int idx = 0;//当前处理到的灵活型任务索引
        int used = 0;//已经使用的咖啡总量

        double save = 0;//已经节省的时间
            
        //记录灵活性任务使用从1到m咖啡节约的时间
        for (int c = 1; c <= m; c++) {

            while (idx < cnt && used + a[idx] <= c) {

                used += a[idx];
                save += b[idx];

                idx++;
            } //先把能完整喝完咖啡的任务用完

            //咖啡不足以继续完全喂给下一个机器人时
            if (idx < cnt) {

                flex[c] = save + (double) b[idx] * (c - used) / a[idx]; 

            }
            //执行完while没有咖啡了 
            else {

                flex[c] = save;
            }
        }

        double best = flex[m];//初始化为咖啡全给灵活任务

        //遍历不同咖啡分给灵活型和普通型的几种情况，时间复杂度O(m)
        for (int usedCoffee = 0;usedCoffee <= maxUsed;usedCoffee++) {

            if (dp[usedCoffee] < 0) continue;//跳过不可达状态

            double cur = dp[usedCoffee] + flex[m - usedCoffee];

            if (cur > best) {
                best = cur;
            }
        }

        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        out.write(String.valueOf(base - best));

        out.flush();
    }
}

我们有 n个任务，总咖啡 m。普通型任务不可分割，也就是0/1 背包问题。灵活型任务消耗a咖啡，可以分割，也就是可以使用贪心。

对于普通任务的0/1背包问题，先设计一个动态规划数组dp，然后再进行数据读入之后，用dp记录在普通任务中，用几个咖啡对应能省多少时间。

else {

                int upper = Math.min(m, maxUsed + ai);//当前任务最多用的咖啡数（不能超过m）

                for (int j = upper; j >= ai; j--) {

                    int nv = dp[j - ai] + bi;

                    if (nv > dp[j]) {
                        dp[j] = nv;
                    }
                }

                maxUsed = upper;
            }
        }

假设：咖啡总量 m = 5 ,第一个普通型任务：ai = 2, bi = 10:

初始状态

dp = [0, -∞, -∞, -∞, -∞, -∞]
maxUsed = 0

处理第一个任务

upper = min(5, 0 + 2) = 2

循环 j 从 2 到 2：

j = 2：nv = dp[0] + 10 = 0 + 10 = 10,dp[2] = 10

更新后：

dp = [0, -∞, 10, -∞, -∞, -∞]
maxUsed = 2

---

第二个普通型任务：ai = 3, bi = 12

upper = min(5, 2 + 3) = 5

循环 j 从 5 到 3：

j = 5：nv = dp[2] + 12 = 10 + 12 = 22，dp[5] = 22。

j = 4:nv = dp[1] + 12 = -∞ + 12（无效)

j = 3：nv = dp[0] + 12 = 0 + 12 = 12 dp[3] = 12

最终结果：

dp = [0, -∞, 10, 12, -∞, 22]
maxUsed = 5

可以看到，用 2 咖啡省 10，用 3 咖啡省 12，用 5 咖啡省 22（同时做两个任务）。

然后用 flex 数组来记录使用从1到 m 咖啡的条件下灵活型任务能节省多少时间。

        double[] flex = new double[m + 1];//存储不同咖啡量下灵活型任务的最大节省时间

        int idx = 0;//当前处理到的灵活型任务索引
        int used = 0;//已经使用的咖啡总量

        double save = 0;//已经节省的时间
            
        //记录灵活性任务使用从1到m咖啡节约的时间
        for (int c = 1; c <= m; c++) {

            while (idx < cnt && used + a[idx] <= c) {

                used += a[idx];
                save += b[idx];

                idx++;
            } //先把能完整喝完咖啡的任务用完

            //咖啡不足以继续完全喂给下一个机器人时
            if (idx < cnt) {

                flex[c] = save + (double) b[idx] * (c - used) / a[idx]; 

            }
            //执行完while没有咖啡了 
            else {
                flex[c] = save;
            }
        }

最后枚举不同咖啡分给普通型和灵活型的每种情况，记录节省时间最多的情况，从而得出答案。

 double best = flex[m];//初始化为咖啡全给灵活任务

        //遍历不同咖啡分给灵活型和普通型的几种情况，时间复杂度O(m)
        for (int usedCoffee = 0;usedCoffee <= maxUsed;usedCoffee++) {

            if (dp[usedCoffee] < 0) continue;//跳过不可达状态

            double cur = dp[usedCoffee] + flex[m - usedCoffee];

            if (cur > best) {
                best = cur;
            }
        }