牛客周赛 Round 110 A ~ E

A

我们不难发现仅当 $n = 1$ 时才是 NO，其余均为 YES，证明的话自己枚举一下就可以发现了。

B

我们不难发现：

$S = \sum^{n}_{i = 1} a_i + \sum^{n - 1}_{i = 2} a_i$

所以我们把最小的两个数放在第一个和最后一个再进行相加即可，具体实现用快速排序然后相加就行了。

时间复杂度 $O(Tn)$ ，可以通过。

C

简单找一下规律即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;
int n, T, a[N], maxn, flag;

int main()
{ 
	cin >> T;
	while (T--)
	{ 
		cin >> n; 
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i]; 
            maxn = max(maxn, a[i]); 
        } 
        for (int i = 1; i <= n; i++)
        { 
            if (maxn == a[i])
            { 
                if (i > 1 && a[i - 1]) flag |= 1;
                if (i < n && a[i + 1]) flag |= 1;
            } 
        } 
        if (flag) cout << maxn <<"\n"; 
        else if (maxn <= 1) cout << -1 << "\n";
        else cout << maxn - 1 << "\n";
        maxn = 0, flag = 0;
    }
    return 0;
}

D

简单贪心，感觉比 C 要简单很多。

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int N = 2e5 + 5;
int n, T, a[N], ans1, ans2;
 
signed main()
{ 
    cin >> T;
    while (T--)
    { 
        cin >> n; 
        for (int i = 1; i <= n; i++) cin >> a[i]; 
        sort(a + 1, a + n + 1);
        if(n % 2 == 1)
        {
            for (int i = 1; i < n; i++) ans1 += abs(a[i] - a[(n + 1) / 2]);
            for (int i = 2; i <= n; i++) ans2 += abs(a[i] - a[(n + 1) / 2]);
            cout << min(ans1, ans2) << "\n";
        }
        else
        {
            for (int i = 1; i < n; i++) ans1 += abs(a[i] - a[n / 2]);
            for (int i = 2; i <= n; i++) ans2 += abs(a[i] - a[n / 2]);
            cout << min(ans1, ans2) << "\n";
        }
        ans1 = ans2 = 0;
    }
    return 0;
}

我们只需要把最大值删去，再进行计算即可。然后我们就可以获得 $120\text{pts}$ 。

那为什么呢？因为有一些特殊情况我们没考虑到，具体可以参考代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5 + 5;
int n, T, a[N], ans1, ans2;

signed main()
{ 
	cin >> T;
	while (T--)
	{ 
		cin >> n; 
        for (int i = 1; i <= n; i++) cin >> a[i]; 
        sort(a + 1, a + n + 1);
        for (int i = 1; i < n; i++) ans1 += abs(a[i] - a[(n + 1) / 2]);
       	for (int i = 2; i <= n; i++) ans2 += abs(a[i] - a[(n + 1) / 2 + 1]);
        cout << min(ans1, ans2) << "\n";
        ans1 = ans2 = 0;
    }
    return 0;
}

我们发现修改了：

for (int i = 1; i < n; i++) ans1 += abs(a[i] - a[(n + 1) / 2]);
for (int i = 2; i <= n; i++) ans2 += abs(a[i] - a[(n + 1) / 2 + 1]);

两行代码就可以通过了，因为我们这里有两种不同的情况，我们需要把两种不同的情况分别计算出来，再取最小值即可，可以通过。

E

小学奥数题，每进一次位，数字和减九，或者模九也可以。

然后考虑优化，我们可以使用前缀和进行优化时间复杂度。

代码具体实现比较复杂，大家可以自己尝试一下。