求一个C++ Problem 的解法

Question

小H觉得回文数字是非常美的，但是现实中遇到的数字串并非全部都是回文，因此小H要将连续若干个数变成回文，例如[2 4 6 4 3]，最少改变数字数量1个，即2改成3或3改成2。但是仅仅这么算作为第四题太简单了，因此要加大难度。出题人除了给你n个数ai外，还给了你一个奇数m。由经验可知n个数可以划分出n-m+1个子串（每个子串个数为m），现在需要你计算出每个子串都转换为回文的变化总次数。当然为了加深小H对题目的理解，出题者对样例进行如下解释，
例如样例中可以生成4个子串，其中第一个子串[2 3 9 3 6]需要变化1次，第二个子串[3 9 3 6 3]需要变化次数为1，第三个子串[9 3 6 3 9]需要变化次数为0，[3 6 3 9 7]需要变化次数为2。所以答案就是1+1+0+2=4。
输入
第一行输入n和m。
第二行输入n个整数ai。
输出
输出所有子串变成回文的变化次数之和
样例输入
8 5
2 3 9 3 6 3 9 7
样例输出
4
数据规模：
70%数据 n<=300
100%数据 1<=m<=n<=10^6 (m保证为奇数) 1<=ai<=10^6

O(nm) 的会超时

Answer 1

O(n)的：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 0; i < (n - m + 1) / 2; ++i) {
        for (int j = 0; j < m / 2; ++j) {
            int x = a[i * m + j];
            int y = a[(i + 1) * m - 1 - j];
            ans += abs(x - y);
        }
    }
    cout << ans << endl;
    return 0;
}