靈能傳輸

友情鏈接：靈能傳輸

題目：

輸入樣例：

3
3
5 -2 3
4
0 0 0 0
3
1 2 3

輸出樣例：

3
0
3

思路：

題目大意：給出一個數(shù)組，每次選擇數(shù)組中的一個數(shù)（要求不能是第一個數(shù)與最后一個數(shù)），如果這個數(shù)是一個正數(shù)，就將這個數(shù)減去自身兩次，并且將相鄰的兩個數(shù)分別加上這個數(shù)一次，如果這個數(shù)是負數(shù)，就將這個數(shù)減去自身兩次，并且將相鄰的數(shù)加上這個負數(shù)兩次，（本質(zhì)上第二種情況與第一種情況一樣，因為減去負數(shù)相當于加上這個負數(shù)的絕對值），使用公式表述為：$a_{i?1}+=a_i{a}_{i+1}+=a_i{a}_i?=2a_i$，并且記住選擇的i不能是第一個數(shù)或最后一個數(shù)。

具體思路：

通過嘗試可知，公式與每一個數(shù)的前綴和有極大的關系，舉例：對于數(shù)組5 -2 3 4而言，其前綴和為5 3 6 10，如果選擇的是-2，那么原數(shù)組的值會變?yōu)?#xff1a;3 2 1 4，變化后的數(shù)組前綴和為：3 5 6 10，相當于將原數(shù)組的前綴和中的第一個位置與第二個位置進行了交換，再看還是對于數(shù)組5 -2 3 4而言，如果選擇的是3，那么原數(shù)組的值會變?yōu)?code>5 1 -3 7，對應的前綴和為5 6 3 10，相當于對原數(shù)組的前綴和數(shù)組的第二個位置與第三個位置進行了交換。下圖為更直觀的理解：

由此我們可以得出一個規(guī)律：如果對某一個位置i進行操作，相當于對前綴和數(shù)組中i與i - 1位置的值進行交換。其中：1 < i < n。

這樣我們就可以得出一個簡單的解決方案了，題目要求的是使原數(shù)組中數(shù)值的絕對值的最大值最小化，一個簡單的思路是對前綴和數(shù)組進行排序，因為這樣可以保證相鄰兩個前綴和數(shù)值的差值最小，這樣就保證了原數(shù)組中的數(shù)值的最大值最小化。

但是題目還有一個條件，就是不能對第一個位置和最后一個位置進行操作，如果直接對前綴和數(shù)組（前綴和數(shù)組表示為：$S$）進行排序（包含了$S_0$和$S_n$），那么就違反了題目的要求。我們這樣思考：如果對$a_1$（原數(shù)組用$a$表示）進行操作，那么對應的前綴和變化是交換$S_0$和$S_1$（其中$S_0=0$ ），如果對$a_n$進行操作，那么對應的前綴和數(shù)組的變化是交換$S_n$和$S_{n?1}$，為了不使$S_0$和$S_n$移動，我們這兩個數(shù)進行移動，我們需要讓起點仍然是因為$S_0$和$S_n$，但為了使相鄰兩個值之間的差值最小，我們需要使用一些策略：如從$S_0$的位置進行步長為2向前進行取值正序填充到一個新的數(shù)組中去并且進行標記，在$S_n$的位置也進行步長為2向后進行取值，逆序（即：從新數(shù)組的最后一個位置開始進行填充）填充到一個新的數(shù)組中去并且進行標記，最后從頭開始遍歷排序后的前綴和數(shù)組，將還未標記的值按順序一次填充到新的數(shù)組的空余位置。

還有一個問題：$S_0$如果大于$S_n$該如何解決？

對于這種情況：我們只需要在查找$S_0$和$S_n$的位置的時候將$S_0$和$S_n$的位置進行交換即可，這樣就變?yōu)榱?span id="ieo6y2aa" class="katex--inline">$S_n$向前進行步長為2的取值，$S_0$向后進行步長為2的移動。下圖為一個直觀的理解：

記得要使用long long數(shù)據(jù)類型，因為int類型的數(shù)據(jù)最大在$10^9$左右，而題目要求的$a_i$的值小于等于$10^9$，其前綴和數(shù)組的值可能會超過int的存儲容量。

代碼：

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
void solve(){int n; cin>>n;vector<ll> A(n + 1, 0);vector<ll> S(n + 1, 0);for(int i = 1;i <= n;i ++){cin>>A[i];S[i] += S[i - 1] + A[i];}// 記錄S中的第一個位置與最后一個位置ll front = S[0];ll end = S[n];if(front > end) swap(front, end);// 對前綴和數(shù)組進行順序排序sort(S.begin(), S.end());   // 排序的時候包含了第0個位置的數(shù) // 找到原來S數(shù)組的第一個位置和最后一個位置的數(shù)在排序后的數(shù)組中的下標for(int i = 0;i <= n;i ++){if(S[i] == front){front = i;break;}}for(int i = n;i >= 0;i --){   // 這里遍歷也可以從0開始到n結束if(S[i] == end){end = i;break;}}vector<ll> ans(n + 1, 0);// 設定標記數(shù)組vector<ll> cnt(n + 1, 0);ll frontidx = 0;ll endidx = n; // 從idxf向前進行找for(int i = front;i >= 0;i -= 2){ans[frontidx++] = S[i];cnt[i] = 1;}// 從idxe向后進行找 for(int i = end;i <=n ;i += 2){ans[endidx --] = S[i];cnt[i] = 1;}// 將剩下的數(shù)進行填充 for(int i = 0;i <= n;i ++){if(!cnt[i]){ans[frontidx++] = S[i];}}// 從ans數(shù)組中找到相鄰兩個數(shù)之間的最小的值ll tans = 0;for(int i = 1;i <= n;i ++){tans = max(tans, abs(ans[i] - ans[i - 1]));}cout<<tans<<endl;return ;
} signed main(){ios::sync_with_stdio(0);cin.tie(0);int t = 1; cin>>t;  // t組詢問 while(t--){solve();}return 0;
}