题解：「COCI 2024.3」Rolete

问题分析

题目要求我们为每个查询 h，计算使所有窗帘的下降高度不超过 h 厘米所需的最短时间。核心思路是枚举手动拉起的窗帘数量，计算对应的最小时间，再取最小值。

关键观察

1. 预处理排序：将窗帘初始高度 a 排序，便于后续分组计算。
2. 手动与同步结合：最优策略是先手动拉起部分窗帘（高度最高的 m 个），再用同步按钮拉起所有窗帘剩余部分。
3. 同步时间计算：同步时，已完全拉起的窗帘会减慢速度。需按拉起高度分段计算时间，利用前缀和优化。

算法步骤

1. 排序与预处理：

   • 对 a 降序排序，得到 sorted_a。
   • 预处理前缀和数组 pre_sum，其中 pre_sum[m] 是前 m 个窗帘的高度和（用于计算手动时间）。
   • 预处理分段时间前缀和数组 cost_prefix，其中 cost_prefix[x] 是同步拉起 x 厘米的总时间（考虑速度减慢）。

2. 查询处理：

   • 对每个查询 h，过滤掉初始高度已满足条件的窗帘。
   • 枚举手动拉起的窗帘数量 m（从 0 到剩余窗帘数），计算：
     • 手动时间：pre_sum[m] - m * h（需拉起的总高度 × 手动速度 t）。
     • 同步时间：cost_prefix[max_h - h]（剩余窗帘需拉起的高度 × 同步速度，分段计算）。
   • 取所有 m 对应的总时间最小值，即为答案。

数学推导

1. 同步时间计算： 同步拉起 x 厘米时，速度随已拉起窗帘数 r 变化：

   • 第 i 段（拉起第 i 厘米）：剩余 n - r 个窗帘，速度为 s + k * r。
   • 总时间为各段时间之和：sum_{i=0}^{x-1} (s + k * min(i, n)) * (n - min(i, n))。
   • 分段优化：前 n 厘米和超过 n 厘米的部分分开计算，利用等差数列求和公式。

2. 前缀和优化：

   • pre_sum[m] 快速计算前 m 个窗帘的手动拉起总高度。
   • cost_prefix[x] 预计算同步拉起 x 厘米的总时间，避免重复计算。

代码实现

n, t, s, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)  # 降序排序

# 预处理前缀和 pre_sum[m] = sum_{i=0 to m-1} a[i]
pre_sum = [0] * (n + 1)
for m in range(1, n + 1):
    pre_sum[m] = pre_sum[m - 1] + a[m - 1]

# 预处理 cost_prefix[x]: 同步拉起 x 厘米的总时间
max_possible_x = max(a) if a else 0
cost_prefix = [0] * (max_possible_x + 2)  # 确保足够大

for x in range(1, max_possible_x + 1):
    if x <= n:
        # 前 x 厘米，每段 r 从 0 到 x-1，每段时间 (s + k*r) * (n - r)
        term = (s + k * (x - 1)) * (n - (x - 1))
        cost_prefix[x] = cost_prefix[x - 1] + term
    else:
        # 超过 n 厘米的部分，每段 r = n，时间 (s + k*n) * 0 = 0
        cost_prefix[x] = cost_prefix[x - 1]

q = int(input())
h_list = list(map(int, input().split()))
ans = []

for h in h_list:
    # 计算需要处理的窗帘数量：初始高度 > h 的
    cnt = 0
    while cnt < n and a[cnt] > h:
        cnt += 1
    if cnt == 0:
        ans.append(0)
        continue
    
    max_h = a[0]  # 剩余窗帘的最大初始高度
    required = max_h - h  # 同步需要拉起的高度
    if required < 0:
        ans.append(0)
        continue
    
    # 枚举手动拉起的数量 m（0 <= m <= cnt）
    min_time = float('inf')
    for m in range(0, cnt + 1):
        # 手动时间：拉起前 m 个窗帘到 h，总高度 (pre_sum[m] - m*h)
        manual = (pre_sum[m] - m * h) * t
        if manual < 0:
            manual = 0  # 避免负数（可能 m*h 超过 pre_sum[m]，但实际不需要拉）
        
        # 同步时间：拉起 required 厘米
        sync = cost_prefix[required] if required <= max_possible_x else cost_prefix[max_possible_x]
        
        total = manual + sync
        if total < min_time:
            min_time = total
    
    ans.append(min_time)

print(' '.join(map(str, ans)))

复杂度分析

• 预处理：
  • 排序：O(n log n)。
  • 前缀和 pre_sum：O(n)。
  • 同步时间前缀和 cost_prefix：O(max_a)（max_a 是窗帘最大初始高度，<= 1e5）。
• 查询处理：
  • 每个查询枚举 m 的数量为 O(cnt)（cnt 是初始高度 > h 的窗帘数，最坏 O(n)）。
  • 总查询复杂度：O(q * n)，但实际中 cnt 较小，且通过排序优化了枚举效率。

优化方向

• 对于 q 和 n 较大的情况（如 1e5），枚举 m 可能超时。可进一步优化为二分查找 m 的最优值，将查询复杂度降为 O(q log n)。
• 预计算 cost_prefix 时，可直接用数学公式计算分段和，避免循环（适用于 max_a 较大的场景）。

总结

本题的核心是枚举手动拉起的窗帘数量，结合预处理的前缀和数组快速计算手动和同步时间，最终取最小值。通过排序和前缀和优化，确保了算法的高效性，能够应对题目中的数据规模。