48分求助,求助大佬
查看原帖
48分求助,求助大佬
635780
BeBanned楼主2023/7/31 07:52

偶数点全WA

一个很清奇的思路但好像并不能面对偶数,并且我也知道怎么错的。。。

如果一个序列可以变成全部相同,那么这个hih_i序列一定可以写成:

a+b1,a+b1+b2,a+b2+b3,……,a+bna+b_1, a+b_1+b_2, a+b_2+b_3, …… , a+b_n

  1. n为奇数,我们可以顺推+逆推解除所有b_i的值,递推公式在代码里,这种情况下,我认为不存在“最小值”一说,因为所有b都是定值,那么a也是定值
  2. n为偶数,这时候可以发现我们只能解出偶数下标的b值,但奇数下标无论怎么解也解不出来,这时候回到概念“最小值”,换句话说,怎么能让a最大还正确呢?求助悬关,谢谢大佬。

// 偶数那部分瞎写的,大佬别看。。。

#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;
}
2023/7/31 07:52
加载中...