Codeforces Round #619 (Div. 2)：B. Motarack's Birthday

电玩女神 2023-07-05 11:41 25阅读 0赞

**Discription**  
Dark is going to attend Motarack’s birthday. Dark decided that the gift he is going to give to Motarack is an array a of n non-negative integers.

Dark created that array 1000 years ago, so some elements in that array disappeared. Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them. He doesn’t have much time so he wants to choose an integer k (0≤k≤109) and replaces all missing elements in the array a with k.

Let m be the maximum absolute difference between all adjacent elements (i.e. the maximum value of |ai−ai+1| for all 1≤i≤n−1) in the array a after Dark replaces all missing elements with k.

Dark should choose an integer k so that m is minimized. Can you help him?

**Input**  
The input consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer n (2≤n≤105) — the size of the array a.

The second line of each test case contains n integers a1,a2,…,an (−1≤ai≤109). If ai=−1, then the i-th integer is missing. It is guaranteed that at least one integer is missing in every test case.

It is guaranteed, that the sum of n for all test cases does not exceed 4⋅105.

**Output**  
Print the answers for each test case in the following format:

You should print two integers, the minimum possible value of m and an integer k (0≤k≤109) that makes the maximum absolute difference between adjacent elements in the array a equal to m.

Make sure that after replacing all the missing elements with k, the maximum absolute difference between adjacent elements becomes m.

If there is more than one possible k, you can print any of them.

**Example**  
**input**

7
    5
    -1 10 -1 12 -1
    5
    -1 40 35 -1 35
    6
    -1 -1 9 -1 3 -1
    2
    -1 -1
    2
    0 -1
    4
    1 -1 3 -1
    7
    1 -1 7 5 2 -1 5

**output**

1 11
    5 35
    3 6
    0 42
    0 0
    1 2
    3 4

**Note**  
In the first test case after replacing all missing elements with 11 the array becomes \[11,10,11,12,11\]. The absolute difference between any adjacent elements is 1. It is impossible to choose a value of k, such that the absolute difference between any adjacent element will be ≤0. So, the answer is 1.

In the third test case after replacing all missing elements with 6 the array becomes \[6,6,9,6,3,6\].

|a1−a2|=|6−6|=0;
    |a2−a3|=|6−9|=3;
    |a3−a4|=|9−6|=3;
    |a4−a5|=|6−3|=3;
    |a5−a6|=|3−6|=3.

So, the maximum difference between any adjacent elements is 3.

**题意**  
有一串非负数，有一些数因为某种原因丢失。要求在丢失处填入一个相同的数，让所有的数中的两个相邻的数之间的差值最小。  
输出最大的差值和填入的数。

**思路**  
遍历数组，找-1两边差值最大一组，取填入的数为两边的平均数。  
在不是-1的某数左边或右边不等于-1时，记录差值，取最大值。  
最后差值与插入的数的左右的数的差值比较，取最大值。

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define sd(n) scanf("%d", &n)
    #define sdd(n, m) scanf("%d%d", &n, &m)
    #define sddd(n, m, k) scanf("%d%d%d", &n, &m, &k)
    #define sld(n) scanf("%lld", &n)
    #define sldd(n, m) scanf("%lld%lld", &n, &m)
    #define slddd(n, m, k) scanf("%lld%lld%lld", &n, &m, &k)
    #define sf(n) scanf("%lf", &n)
    #define sff(n, m) scanf("%lf%lf", &n, &m)
    #define sfff(n, m, k) scanf("%lf%lf%lf", &n, &m, &k)
    #define pd(n) printf("%d\n", (n))
    #define pdd(n, m) printf("%d %d\n", n, m)
    #define pld(n) printf("%lld\n", n)
    #define pldd(n, m) printf("%lld %lld\n", n, m)
    #define rep(i, a, n) for(int i=a; i<=n; i++)
    #define per(i, n, a) for(int i=n; i>=a; i--)
     
     
    int T;
    int n;
    int a[100001];
    int c,ans;
     
    int main()
    { 
        scanf("%d",&T);
        while(T--)
        { 
            sd(n);
            for(int i=1; i<=n; i++)
                sd(a[i]);
            a[0]=-1,a[n+1]=-1,c=0;
            int k=1,tmp=-1,tt=0,q=1,f=-1;
            int l=1e9+1;
            int r=0;
            for(int i=1;i<=n;i++)
            { 
                if(a[i]!=-1)
                { 
                    f=a[i];
                    if(a[i+1]!=-1)
                        c=max(abs(a[i+1]-a[i]),c);
                    if(a[i-1]!=-1)
                        c=max(abs(a[i]-a[i-1]),c);
                        //continue;
                }
                else
                { 
                    if(a[i-1]!=-1)
                    { 
                        l=min(a[i-1],l);
                        r=max(a[i-1],r);
                    }
                    if(a[i+1]!=-1)
                    { 
                        l=min(a[i+1],l);
                        r=max(a[i+1],r);
                    }
                }
            }
            ans=(l+r+1)/2;
            c=max(abs(r-ans),c);
            c=max(abs(ans-l),c);
            if(f==-1)
            { 
                cout<<0<<" "<<42<<endl;
                continue;
            }
            cout<<c<<" "<<ans<<endl;
        }
        return 0;
    }