题目分析

有 $N$ 个州，$K$ 张选票目标。对于每个州可以选择：

• 只获得选票：演讲 $A_i$ 小时获得 1 张选票
• 获得选票+协作者：演讲 $B_i$ 小时获得 1 张选票 + 1 个协作者（$B_i = -1$ 表示无法获得协作者）

协作者作用：可以与你同时在不同州演讲，时间叠加计算。即如果有 $t$ 个协作者（包括自己），演讲 1 小时相当于该州获得 $t$ 小时的演讲量。

目标：最小化总演讲时间。

核心思路

动态规划 + 枚举框架

枚举最终协作者数量 $T$（包括自己），对每个 $T$ 计算最小时间。

double ans = INF;
for (int T = 0; T <= n; T++) {
    // DP计算前i个州获得j个协作者的最小时间
    // 贪心补足剩余选票
    ans = min(ans, total_time);
}

状态设计与转移

DP状态：f[i][j] 表示考虑前 $i$ 个州（按 $B_i$ 排序），已经获得 $j$ 个协作者的最小时间。

转移方程：

• 不获得协作者：f[i][j] = min(f[i][j], f[i-1][j] + A_i/(T+1))
• 获得协作者：f[i][j] = min(f[i][j], f[i-1][j-1] + B_i/j)

贪心补足策略

用剩余州中 $A_i$ 最小的来补足 $K$ 张选票：

double additional_time = prefix_sum[i+1][remaining_votes] / (T + 1);

代码详解

预处理与排序

// 输入处理
for (int i = 1; i <= n; i++) {
    cin >> states[i].a >> states[i].b;
    if (states[i].b == -1) {
        states[i].b = INF;  // 标记无法获得协作者
    }
}

// 按B_i排序，优先获得便宜的协作者
sort(states + 1, states + n + 1, compareByB);

// 预处理后缀区间的最小A_i前缀和
for (int start = n; start >= 1; start--) {
    Node temp[N];
    for (int j = start; j <= n; j++) temp[j] = states[j];
    sort(temp + start, temp + n + 1, compareByA);
    for (int len = 1; len <= n - start + 1; len++) {
        prefix_sum[start][len] = prefix_sum[start][len - 1] + temp[start + len - 1].a;
    }
}

动态规划核心

for (int T = 0; T <= n; T++) {
    vector<vector<double>> f(n + 1, vector<double>(T + 1, INF));
    f[0][0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= T; j++) {
            // 选择1：只获得选票
            f[i][j] = min(f[i][j], f[i - 1][j] + states[i].a / (T + 1));
            
            // 选择2：获得选票+协作者
            if (j > 0 && states[i].b < INF) {
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + states[i].b / j);
            }
        }
    }
    
    // 贪心补足剩余选票
    for (int i = T; i <= n; i++) {
        int remaining_votes = K - i;
        if (remaining_votes < 0 || remaining_votes > n - i) continue;
        
        double total_time = f[i][T] + prefix_sum[i + 1][remaining_votes] / (T + 1);
        ans = min(ans, total_time);
    }
}

算法正确性

排序策略

按 $B_i$ 升序排序确保优先获得便宜的协作者，这是最优的，因为：

• 协作者能加速后续所有州的演讲
• 先获得便宜的协作者性价比最高

状态转移

准确记录了获得协作者的数量对演讲效率的影响：

• 分母 $T+1$ 表示最终协作者数量（包括自己）
• 分母 $j$ 表示获得协作者时的当前协作者数量

贪心补足

用最小的 $A_i$ 补足选票是最优策略，因为：

• 这些州无法获得协作者
• 选择演讲时间最短的州最节省时间

复杂度分析

• 时间复杂度：$O(N^3)$

  • 外层枚举 $T$：$O(N)$
  • DP过程：$O(N^2)$
  • 预处理：$O(N^2 \log N)$
  • 对于 $N \leq 500$ 可接受

• 空间复杂度：$O(N^2)$ 存储DP状态和前缀和

样例验证

样例1

n=3, k=3
A=[1,2,4], B=[5,3,5]

输出：5.5

验证：在州2演讲3小时获得协作者，然后并行完成州3和州1。

样例2

n=7, k=4  
A=[4,11,6,12,36,11,20], B=[-1,-1,-1,-1,-1,-1,-1]

输出：32.0

验证：选择4个最小的A_i：4+6+11+11=32。

总结

本题是典型的动态规划 + 贪心 + 枚举问题：

1. 枚举框架：枚举最终协作者数量
2. 动态规划：计算获得协作者的最优方案
3. 贪心补足：用最小代价补足剩余选票
4. 排序优化：优先获得便宜协作者

这种解法充分利用了问题的特殊结构，通过合理的状态设计和贪心策略，在多项式时间内解决了复杂的调度优化问题。