造题计划（下）

形式化题目

有 $n$ 天，每天上午小 C 至多造一题（花费 $a_i$ ），下午小 F 至多验一题（花费 $b_i$ ）。一题必须先造后验，且造和验可在同一天完成。两人总花费不得超过 $m$ ，求最多能完成的题目数。

思路

"已造未验"的题目数称为余额，它天然形成 DP 状态。先看枚举每天四种选择的朴素做法：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 23:03
 */
// brute.cpp：递归枚举每天不工作、造题、验题或两人都工作的选择。
#include <bits/stdc++.h>
using namespace std;

int n;
long long budget;
vector<long long> make_cost;
vector<long long> check_cost;
int answer;

void dfs(int day, int balance, long long cost, int count) {
    if (cost > budget) {
        return;
    }
    if (day == n + 1) {
        if (balance == 0) {
            answer = max(answer, count);
        }
        return;
    }
    dfs(day + 1, balance, cost, count);
    dfs(day + 1, balance + 1, cost + make_cost[day], count);
    if (balance > 0) {
        dfs(day + 1, balance - 1, cost + check_cost[day], count + 1);
    }
    dfs(day + 1, balance,
        cost + make_cost[day] + check_cost[day], count + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> budget;
    make_cost.assign(n + 1, 0);
    check_cost.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> make_cost[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> check_cost[i];
    }
    dfs(1, 0, 0, 0);
    cout << answer << '\n';
    return 0;
}

拉格朗日奖励

给每完成一题加奖励 $\lambda$ ，相当于验题费用变成 $b_i - \lambda$ 。设 $F_i[h]$ 为处理完前 $i$ 天、余额为 $h$ 时的最小调整费用。关键性质是 $F_i[h]$ 关于 $h$ 是离散凸函数，可以用相邻斜率 $D_h = F_i[h]-F_i[h-1]$ 完整描述。

一天内的斜率变化

一天的四种选择（不工作、造题、验题、同天造+验）会让斜率序列只发生常数次修改：

先取 center = min(0, a_i + b_i - λ)；
若最小斜率小于 lower = center - (b_i - λ)，弹出最小斜率并插入 lower，同时调整 $F(0)$ ；
插入 upper = a_i - center。

用一个斜率小根堆即可完成，每天 $O(\log n)$ 。斜率相同时需要保留"优先选择的题数"信息，因此堆元素是 $(费用, 题数)$ 二元组。

二分奖励

$F_n[0]$ 给出固定 $\lambda$ 下 $cost - \lambda \cdot count$ 的最小值，恢复出实际花费。 $\lambda$ 增大时最优题数单调不减，可以二分。最后在相邻两个奖励点之间按边际花费线性插值，得到预算内能完成的最大题数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 23:03
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500000;

struct PairValue {
    long long cost;
    long long negative_count;
};

struct PairGreater {
    bool operator()(const PairValue &x, const PairValue &y) const {
        if (x.cost != y.cost) {
            return x.cost > y.cost;
        }
        return x.negative_count > y.negative_count;
    }
};

struct Evaluation {
    long long count;
    long long real_cost;
};

int n;
long long budget;
long long make_cost[MAXN + 1];
long long check_cost[MAXN + 1];

PairValue add_pair(const PairValue &x, const PairValue &y) {
    return {x.cost + y.cost, x.negative_count + y.negative_count};
}

PairValue subtract_pair(const PairValue &x, const PairValue &y) {
    return {x.cost - y.cost, x.negative_count - y.negative_count};
}

bool pair_less(const PairValue &x, const PairValue &y) {
    if (x.cost != y.cost) {
        return x.cost < y.cost;
    }
    return x.negative_count < y.negative_count;
}

// 对给定奖励 reward_twice 求最优解。
// 函数值存 2 倍，避免除 2 丢失精度；count 为完成题数，real_cost 为真实花费。
Evaluation evaluate(long long reward_twice) {
    priority_queue<PairValue, vector<PairValue>, PairGreater> slopes; // 斜率小根堆
    PairValue function_at_zero = {0, 0}; // F(0)：余额为 0 时的最小调整费用

    for (int day = 1; day <= n; day++) {
        // 当天的四种选择，用斜率序列的常数次堆操作完成转移（详见题解推导）
        PairValue idle = {0, 0};
        PairValue both = {2LL * (make_cost[day] + check_cost[day])
                              - reward_twice, -1};
        PairValue center = pair_less(both, idle) ? both : idle;
        PairValue down = {2LL * check_cost[day] - reward_twice, -1};
        PairValue up = {2LL * make_cost[day], 0};
        PairValue lower = subtract_pair(center, down);
        PairValue upper = subtract_pair(up, center);

        function_at_zero = add_pair(function_at_zero, center);
        if (!slopes.empty() && pair_less(slopes.top(), lower)) {
            PairValue smallest = slopes.top();
            slopes.pop();
            function_at_zero = add_pair(function_at_zero,
                                         subtract_pair(smallest, lower));
            slopes.push(lower);
        }
        slopes.push(upper);
    }

    long long count = -function_at_zero.negative_count;
    long long real_cost_twice = function_at_zero.cost + reward_twice * count;
    return {count, real_cost_twice / 2};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> budget;
    long long maximum_reward = 0;
    for (int i = 1; i <= n; i++) {
        cin >> make_cost[i];
        maximum_reward = max(maximum_reward, make_cost[i]);
    }
    for (int i = 1; i <= n; i++) {
        cin >> check_cost[i];
        maximum_reward = max(maximum_reward, check_cost[i]);
    }

    // 二分奖励值，找到实际花费不超过预算的最大完成题数
    long long low = 0;
    long long high = 1;
    while (evaluate(high).count < n) {
        high *= 2;
    }
    while (low < high) {
        long long middle = (low + high + 1) / 2;
        Evaluation current = evaluate(middle);
        if (current.real_cost <= budget) {
            low = middle;
        } else {
            high = middle - 1;
        }
    }

    // 奖励不是整数时的修正：在相邻两个奖励点之间按边际花费线性插值
    Evaluation left = evaluate(low);
    if (left.count == n) {
        cout << n << '\n';
        return 0;
    }

    Evaluation right = evaluate(low + 1);
    if (right.real_cost <= budget) {
        cout << right.count << '\n';
        return 0;
    }
    if (right.count == left.count) {
        cout << left.count << '\n';
        return 0;
    }
    long long marginal = (right.real_cost - left.real_cost)
                         / (right.count - left.count);
    long long extra = (budget - left.real_cost) / marginal;
    extra = min(extra, right.count - left.count);
    cout << left.count + extra << '\n';
    return 0;
}

复杂度

一次拉格朗日求解为 $O(n \log n)$ ，二分奖励后总复杂度 $O(n \log n \log V)$ ，空间复杂度 $O(n)$ 。

总结

先造后验的约束形成余额 DP，其离散凸性使整张状态表压缩成有序斜率。拉格朗日奖励把"预算内最大数量"转成一维参数搜索，是解决此类凸优化计数问题的通用套路。

子任务编号	分值	$n\le$
1	20	$100$
2	30	$3000$
3	20	$10^5$
4	30	$5\times 10^5$

目录

形式化题目

思路

拉格朗日奖励

一天内的斜率变化

二分奖励

代码

复杂度

总结