前言：哎，這場打的就很nanshou，開局a出倆題，剩下的數學題興趣就直接無了，結果倆小時直接結束戰斗，
結束之后看了一下題解，感覺D題講的有點麻煩，這邊講一下一種更低效率不過更加直觀的做法，如果有看不懂題解的朋友可以嘗試一下我的理解，
正文開始#
沒看過題目的可以去牛客先看一下，我這里自己出一組資料，
1
5 2
3 3 2 0 2
這里介紹一個演算法，差分演算法，至于為什么想到的，只能說看到這題就本能的就想到這個演算法，
我們對資料進行差分（就是前一個數減后一個數），得到差分陣列cut，
0 1 2 -2
然后我們從左到右推，每次遇到一個數 cut[i] 為正就讓cut [ i+k ]加上cut [ i ],cut [i] = 0，注意這里的i+k必須小于等于n(這里是5)，至于為什么后面解釋，
然后變成了
0 0 0 -1（2）(最后一個2是前面推來的，在位置n上，我們不需要這個數)
然后從右往左，每次遇到cut [ i ]為負數就讓cut [ i - k ] += cut [ i ]，cut [ i ] = 0，注意i+k>=0，
然后變成
(-1) 0 0 0 0 (2)
這里面的位置為1到4都是0，所以可以得出結果，
然后解釋一下我們為什么做這種操作，我下面列一些變化程序，
3 3 2 0 2 cut：0 1 2 -2
3 3 3 1 2 cut：0 0 2 -1
3 3 3 3 4 cut：0 0 0 -1 (2)
3 3 4 4 4 cut：0 -1 0 0 (2)
4 4 4 4 4 cut：(-1) 0 0 0 0 (2)
懂了吧？因為一次操作的區間為k，所以差分陣列會變化的只有i和i+k或i和i-k，
假如i+k>n或者i-k<0,則是不可能的，我們也舉個例子，
k=2，3 4 4 4 4 ， cut：-1 0 0 0
我們就無法把這個-1給清除掉，因為這涉及陣列外的數了，
下面給出代碼，速度還有很大的空間可以優化，但是沒必要
//
// Created by acer on 2021/2/21.
//
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int num[maxn];
int cut[maxn];
signed main() {
int T;
cin >> T;
while (T--) {
memset(cut, 0, sizeof(cut));
int n, k;
int sum = 0;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> num[i];
if (i >= 2)
cut[i - 1] = num[i - 1] - num[i];
}
for (int j = 1; j <= n - 1; ++j) { //正推
if (cut[j] < 0) {
if (j - k < 0) continue;
} else {
if (j + k <= n) {
sum += cut[j];
cut[j + k] += cut[j];
cut[j] = 0;
}
}
}
for (int i = n - 1; i >= 1; --i) { //反推
/*for (int j = 1; j <= n - 1; ++j) {
cout << cut[j] << ' ';
}
cout << endl;*/
if (cut[i] < 0) {
if (i - k > 0) {
cut[i - k] += cut[i];
sum += abs(cut[i]);
cut[i] = 0;
} else if (i - k == 0) {
sum += abs(cut[i]);
cut[i] = 0;
} else if (i - k < 0) {
break;
}
}
}
int l;
for (l = 1; l <= n - 1; ++l) {
if (cut[l] != 0) break;
}
if (l != n)
cout << -1 << endl;
else {
cout << sum << endl;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263002.html
標籤：其他