核心思想

使用滑动窗口 + 前缀和，将窗口移动时的成本更新优化到O(1)。

关键观察

当窗口从[i, i+m-1]滑动到[i+1, i+m]时：

• 正序成本变化：移除权重为1的a[i]，所有其他元素权重减1，添加权重为m的a[i+m]
• 逆序成本关系：逆序成本 = (m+1) × 区间和 - 正序成本

滑动窗口更新公式

设当前窗口[i, i+m-1]的正序成本为forward_cost，则：

新正序成本 = forward_cost - 区间和[i, i+m-1] + m × a[i+m]

其中区间和可以用前缀和O(1)计算。

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

代码实现

Python

def solve():
    # 读取输入
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    
    # 扩展数组以处理环形结构
    extended = a + a[:m]
    
    # 计算前缀和
    prefix = [0] * (len(extended) + 1)
    for i in range(len(extended)):
        prefix[i + 1] = prefix[i] + extended[i]
    
    def get_sum(l, r):
        """计算区间[l,r]的和（0-indexed）"""
        return prefix[r + 1] - prefix[l]
    
    # 计算第一个窗口[0, m-1]的正序成本
    forward_cost = sum((j + 1) * extended[j] for j in range(m))
    
    min_cost = float('inf')
    
    # 枚举所有窗口起始位置
    for i in range(n):
        # 计算当前窗口的逆序成本
        window_sum = get_sum(i, i + m - 1)
        reverse_cost = (m + 1) * window_sum - forward_cost
        
        # 更新最小成本
        min_cost = min(min_cost, forward_cost, reverse_cost)
        
        # 滑动窗口：更新到下一个位置的正序成本
        if i < n - 1:  # 避免数组越界
            # 移除当前窗口的贡献，添加新元素的贡献
            forward_cost = forward_cost - window_sum + m * extended[i + m]
    
    print(min_cost)

solve()

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        // 扩展数组以处理环形结构
        int[] extended = new int[n + m];
        for (int i = 0; i < n; i++) {
            extended[i] = a[i];
        }
        for (int i = 0; i < m; i++) {
            extended[n + i] = a[i];
        }
        
        // 计算前缀和
        long[] prefix = new long[extended.length + 1];
        for (int i = 0; i < extended.length; i++) {
            prefix[i + 1] = prefix[i] + extended[i];
        }
        
        // 计算第一个窗口[0, m-1]的正序成本
        long forwardCost = 0;
        for (int j = 0; j < m; j++) {
            forwardCost += (long)(j + 1) * extended[j];
        }
        
        long minCost = Long.MAX_VALUE;
        
        // 枚举所有窗口起始位置
        for (int i = 0; i < n; i++) {
            // 计算当前窗口的区间和
            long windowSum = prefix[i + m] - prefix[i];
            
            // 计算逆序成本
            long reverseCost = (long)(m + 1) * windowSum - forwardCost;
            
            // 更新最小成本
            minCost = Math.min(minCost, Math.min(forwardCost, reverseCost));
            
            // 滑动窗口：更新到下一个位置的正序成本
            if (i < n - 1) {
                forwardCost = forwardCost - windowSum + (long)m * extended[i + m];
            }
        }
        
        System.out.println(minCost);
        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // 读取输入
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 扩展数组以处理环形结构
    vector<int> extended(n + m);
    for (int i = 0; i < n; i++) {
        extended[i] = a[i];
    }
    for (int i = 0; i < m; i++) {
        extended[n + i] = a[i];
    }
    
    // 计算前缀和
    vector<long long> prefix(extended.size() + 1, 0);
    for (size_t i = 0; i < extended.size(); i++) {
        prefix[i + 1] = prefix[i] + extended[i];
    }
    
    // 计算第一个窗口[0, m-1]的正序成本
    long long forwardCost = 0;
    for (int j = 0; j < m; j++) {
        forwardCost += (long long)(j + 1) * extended[j];
    }
    
    long long minCost = LLONG_MAX;
    
    // 枚举所有窗口起始位置
    for (int i = 0; i < n; i++) {
        // 计算当前窗口的区间和
        long long windowSum = prefix[i + m] - prefix[i];
        
        // 计算逆序成本
        long long reverseCost = (long long)(m + 1) * windowSum - forwardCost;
        
        // 更新最小成本
        minCost = min(minCost, min(forwardCost, reverseCost));
        
        // 滑动窗口：更新到下一个位置的正序成本
        if (i < n - 1) {
            forwardCost = forwardCost - windowSum + (long long)m * extended[i + m];
        }
    }
    
    cout << minCost << endl;
    
    return 0;
}

题目内容

为了迎接即将到来的$2025$星穹铁道演唱会，米小游团队承担了舞台的布置工作。

舞台视为一个圆柱体，等分为 $n$ 块位置。每块位置建造台阶的成本为 $a_i$ 。

你需要在这些位置中选择连续的 $m$ 块进行建造(由于是圆形舞台，所以位置 $n$ 与位置 $1$ 也是相邻的)。记这连续的 $m$ 块成本组成数组 $b=${ $b_1,b_2,...,b_m$ }，你可以按正序或逆序的顺序建造。

若按正序建造，总成本为$\sum^m_{j=1}j×b_j$；若按逆序建造，总成本为 $\sum^m_{j=1}j×b_{m+1-j}$。

请计算并输出最小的建造成本。

输入描述

第一行输入两个整数 $n,m(1≦m≤n≦2×10^5)$ ，分别表示舞台等分块数和需要选择的块数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦ 10^5)$ 表示每块建造台阶的成本。

输出描述

输出一个整数，表示最小建造成本。

样例1

输入

5 3
1 4 3 1 2

输出

8

说明

在第一个样例中，选择位置 $4,5,1$ (对应成本 $b =${ $1,2,1$ })时，正序逆序建造的总成本一样小，等于 $1×1+2×2+3×1=8$ 。

样例2

输入

5 1
3 1 4 1 5

输出

1

说明

在第二个样例中，$m =1$ ，直接选择成本最小的块，得到最小成本 $1$ 。