Codeforces C. Andrew and Stones

 

The main idea of the topic ： An operation is defined as follows ： Choose three subscripts at a time 1<=i<j<k<=n, hold a[j] The value of the reduction 2 Then give each a[i] and a[k] Add 1

Ask if you can put 2~n-1 All elements of the are attributed to 0, If you can , Minimum number of outputs

Ideas ： There are many details about this topic , It needs to be well thought out , Otherwise it's easy wa, First of all, when reading in, check whether there are even numbers . If there is , There is a solution anyway , because Even numbers can go back to 0, In this way, you can always come up with 1 individual 1 To round up odd numbers into even numbers . without , It doesn't matter , because Greater than 1 The odd number of can also be subtracted , Then take out 1 individual 1 Go round other odd numbers , But pay attention to , Greater than 1 The odd number of cannot be returned by itself 0, Need one 1 To return 0, therefore If there is no even number , That's bigger than that 1 The odd number of must appear at least 2 Time . Be careful not to worry about how many times odd or even numbers appear , As long as the minimum standards are met , such as 1 An even number and then 999 Odd or direct 1000 An odd number , It doesn't matter , because Any one greater than 1 The positive integers of can be rounded up to two even numbers , Regardless of parity , So this can have a chain reaction .

Let's talk about how to make the operation smaller , It's actually the normal division of even numbers 2, Odd numbers are divided by one more time , Obviously there can be no smaller operation , Because it needs to be distributed to other numbers besides rounding up even numbers 1, The rest is normal except , The normal division must be thrown directly to both sides .

Code：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

#define int long long

using namespace std;
const int N = 1e6;
int a[N];
void solve()
{
    int n;
    scanf("%lld", &n);
    
    bool flag=true;
    for(int i=1;i<=n;i++) 
    {
        scanf("%lld",&a[i]);
        if(a[i]%2) flag=true;
    }
    
    bool ok=false;
    int ans=0;
    for(int i=2;i<=n-1;i++)
    {
        if(a[i]%2)
        {
            ans+=a[i]/2+1;
            if(a[i]>1&&n>3) ok=true;
        }
        else
        {
            ans+=a[i]/2;
            ok=true;
        }
    }
    
    if(flag)
    {
        if(ok) printf("%lld\n",ans);
        else
        puts("-1");
    }
    else
    printf("%lld\n",ans);

}
signed main()
{
    int _;
    scanf("%lld",&_);
    while(_--) solve();
    return 0;
}