一个很清奇的思路但好像并不能面对偶数,并且我也知道怎么错的。。。
如果一个序列可以变成全部相同,那么这个hi序列一定可以写成:
a+b1,a+b1+b2,a+b2+b3,……,a+bn
// 偶数那部分瞎写的,大佬别看。。。
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll a[100005];
ll b[100005];
void tester(ll n)
{
for(ll i = 1;i <= n;i ++)
{
cout << b[i] << " ";
}
}
int main()
{
ll T;
cin >> T;
while(T --)
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
ll n;
cin >> n;
for(ll i = 1;i <= n;i ++) cin >> a[i];
if(n % 2 == 0)
{
bool flag = true;
for(ll i = 2;i < n;i += 2)
{
b[i] = a[i] - a[i - 1] + b[i - 2];
if(b[i] < 0) flag = false;
}
for(ll i = n - 1;i >= 1;i -= 2)
{
b[i] = a[i] - a[i + 1] + b[i + 2];
if(b[i] < 0) flag = false;
}
ll standar = a[n] - b[n - 1];
if(standar < 0) flag = false;
ll ans = 0;
for(ll i = 1;i <= n;i ++)
{
if(a[i] < standar) flag = false;
ans += 2 * (a[i] - standar);
a[i + 1] -= a[i] - standar;
a[i] = standar;
}
if(a[n] != standar) flag = false;
if(flag) cout << ans << endl;
else cout << -1 << endl;
}
if(n % 2 == 1)
{
bool flag = true;
for(ll i = 2;i < n;i += 2)
{
b[i] = a[i] - a[i - 1] + b[i - 2];
if(b[i] < 0) flag = false;
}
for(ll i = n;i >= 1;i -= 2)
{
b[i] = a[i] - a[i + 1] + b[i + 2];
if(b[i] < 0) flag = false;
}
ll standar = a[n] - b[n - 1];
if(standar < 0) flag = false;
ll ans = 0;
for(ll i = 1;i <= n;i ++)
{
if(a[i] < standar) flag = false;
ans += 2 * (a[i] - standar);
a[i + 1] -= a[i] - standar;
a[i] = standar;
}
if(a[n] != standar) flag = false;
if(flag) cout << ans << endl;
else cout << -1 << endl;
}
}
return 0;
}