题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。
每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

一开始$cnt=0$。有两种操作，每种都可以执行任意次。

• 第一种：把一个大于$0$的$a[i]$减少$1$，然后$cnt$自增。
• 第二种：把一个大于等于$cnt$的$a[i]$减少$cnt$，然后$cnt=0$。

把所有$a[i]$都变成$0$，最少要操作多少次？

输入样例

4
4
1 3 1 1
4
1 2 1 1
6
3 2 1 5 2 4
2
1 6

输出样例

4
4
11
5

算法

贪心

一开始读了个假题，以为操作$2$能把所有$\geq cnt$的数都减少$cnt$，卡好久过不了样例但是又不知道错哪。一定要仔细读题！

其实没想太明白这样贪为什么一定对，但是直觉上觉得应该在一个有序结构上操作更方便，每次把小的数先利用操作$1$减$1$，减到满足“$cnt=$最大值”了就执行一次操作$2$把这个最大值干掉。

按照这种思路，我们可以先把所有元素都放入到一个平衡树中，初始化$cnt=0$。每次检查$cnt+$最小值与最大值的关系。分为以下三种情况：

1. $cnt+minimum \lt maximum$，直接让$cnt$增加$minimum$，操作数也增加$minimum$，将$minimum$从平衡树中删除。
2. $cnt+minimum = maximum$，让$cnt=0$，操作数先增加$minimum$（操作$1$），再增加$1$（操作$2$干掉$maximum$），将$minimum$和$maximum$都从平衡树中删除。
3. $cnt+minimum \gt maximum$，让$cnt=0$，操作数先增加$maximum-cnt$（操作$1$），再增加$1$（操作$2$干掉$maximum$），将$minimum$和$maximum$都从平衡树中删除。但此时最小值并没有完全被减成$0$，而是$minimum-(maximum-cnt)$，因此还要将剩下的部分放入到平衡树中。

当平衡树中只有一个数的时候退出这个过程，根据剩余的数$last$与$cnt$的关系来决定最后一步。分为以下两种情况：

1. $cnt \gt last$，此时只能用操作$1$，让操作数增加$last$。
2. 否则让$cnt$增加$x$，这个$x$是满足$cnt+x \leq last-x$的最大$x$，这样就能保证在使用操作$2$时能够尽量让$last$接近$0$。先执行$x$次操作$1$，然后执行一次操作$2$使$last$变为$last-x-(cnt+x)$。最后$last$还剩多少就要执行多少次操作$1$。

复杂度分析

时间复杂度

在贪心的过程中每个数都要从平衡树中被删除，最多两次就能把一个数删掉（多数情况下一次就删掉了），因此一共删了$O(n)$次。而平衡树的插入和删除操作时间复杂度为$O(log_2n)$，所以整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

额外空间就是平衡树所消耗的空间，为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int t, n, a[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        multiset<int> st;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            st.insert(a[i]);
        }
        LL cnt = 0, ans = 0;
        while(st.size() > 1) {
            int cur = *st.begin(), mx = *st.rbegin();
            if(cnt + cur < mx) {
                cnt += cur, ans += cur;
                st.erase(st.find(cur));
            }else {
                st.erase(st.find(cur));
                st.erase(st.find(mx));
                ans++;
                if(cnt + cur > mx) {
                    ans += mx - cnt;
                    st.insert(cnt + cur - mx);
                }else {
                    ans += cur;
                }
                cnt = 0;
            }
        }
        if(st.size()) { 
            int last = *st.begin();
            if(cnt <= last) {
                int x = last - cnt >> 1;
                last -= x, cnt += x, ans += x;
                if(cnt > 0) {
                    last -= cnt;
                    ans++;
                }
                ans += last;
            }else {
                ans += last;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}