alisa为了督促自己学习所以写点题解，如果能帮到补题的你就再好不过了。

头文件参考

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(x) (x).begin(), (x).end()

A

一个正整数 要么是奇数 要么是偶数；其中 偶数可以用若干个2表示，奇数可以用若干个2外加一个1来表示，本题中没有1 所以选择去掉一个2加一个3。

特别的，如果本来一个2都没有 那 去2加3 的操作 就无法成立 此时输出-1。

void solve()
{
    int n;
    cin >> n;
    if (n < 2)
    {
        cout << "NO";
    }
    else
    {
        cout << "YES";
    }
}

B

观察结构发现 除了最角落的两个数字外，每一个数字都能作出 次贡献，这启发我们算出总和 然后减去最角落的两个数字即为答案

要使答案最大化，我们应该把最小的两个数字放到角落。

void solve()
{
    int n;
    cin >> n;
	vector<int> v(n + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> v[i];
	}
	
	sort(all(v));
	cout << accumulate(all(v), 0ll) - v[1] - v[2];
}

C

区间越小，mex的值越有可能变小。所以我们枚举每一个 的区间 手动计算 即可，时间复杂度 

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n + 1);

    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }

    // 只要遍历一遍就行
    int ans = LLONG_MIN;
    for (int i = 1; i + 1 <= n; i++)
    {
        int n1 = v[i], n2 = v[i + 1];
        int maxnum = max(n1, n2);
        int mex = 0;
        if (n1 == 0 or n2 == 0)
        {
            mex++;
            if (n1 == 1 or n2 == 1)
            {
                mex++;
            }
        }
        ans = max(ans, maxnum - mex);
    }
    cout << ans;
}

D

看到绝对值想到把它展开。

具体来说，

这样一拆，我们就能把绝对值转化为线性形式：

  • 左边部分：
  • 右边部分： 这就能用前缀和快速计算，而不用每次循环去算所有差值。复杂度从 降低到了

知道了这个知识，现在让我们来看中位数会如何改变。

假设数组长度 n。删去一个数后，剩下 n−1 个数，新的中位数位置就是：

(0 based)

所以：

  • 新中位数一定是 排序后第 m 个数，不过需要跳过被删掉的那个。 换句话说：
    删去不同的数，中位数可能是 相邻的两个元素之一。 例子：
  • n=5，原数组排序后中位数是下标 2。删掉一个数后：
    • 新长度=4 → 新中位数在下标 1。
    • 如果删掉原来排在前半部分的数，中位数候选是原数组的第 2 位；
    • 如果删掉后半部分的数，中位数候选是原数组的第 1 位。

因此，中位数的可能性非常有限。

总体思路总结：

  1. sort
  2. 枚举删除哪个数（n 次）。
  3. 每次确定新的中位数位置（下标 m），并对应到原数组：
    • 如果删除点在中位数左边，新中位数要右移一位。
    • 否则就是当前位置。
  4. 用前缀和在 算新平衡度。
  5. 取最小值。 总体时间复杂度 
void solve()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(all(v));
    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; i++)
    {
        pre[i + 1] = pre[i] + v[i];
    }
    int m_new = (n - 2) / 2;
    int ans = LLONG_MAX;
    for (int k = 0; k < n; k++)
    {
        int pos = m_new + (m_new >= k ? 1 : 0);
        int cur = v[pos];
        int sum_l = pre[pos] - (k < pos ? v[k] : 0);
        int cnt_l = pos - (k < pos ? 1 : 0);
        int sum_r = (pre[n] - pre[pos + 1]) - (k > pos ? v[k] : 0);
        int cnt_r = (n - pos - 1) - (k > pos ? 1 : 0);
        int tot = cur * cnt_l - sum_l + sum_r - cur * cnt_r;
        ans = min(ans, tot);
    }
    cout << ans;
}

E

正在写喵

F

正在写喵