Ex-Capoo Stack

此问题在原题上进行了加强修改(不可改变Capoo顺序)

Problem Statement

有 $n$ 只可爱的 Capoo 想玩叠叠乐，每只 Capoo 都有一个体力值 $a_i$ 。为了防止在叠叠乐的过程中 Capoo 受到伤害，Capoo 们相互约定，除了在最上面的 Capoo ，每只 Capoo 的体力值要大于等于它上面的所有 Capoo 的体力值之和。 Capoo 们自然希望参与叠叠乐的 Capoo 数量最多，所以它们向你提出了一个问题，在不可以改变原有 Capoo 顺序的情况下，参与叠叠乐的 Capoo 数量最多为多少？

Input

本题包含多组测试数据。输入第一行一个整数 $T$ ，表示测试数据组数。（$1 \leq T \leq 2 \times 10^5$）对于每组数据，第一行一个整数 $n$ ，表示 Capoo 数量。（$1 \leq n \leq 2 \times 10^5$）第二行 $n$ 个整数 $a_i$ ，第 $i$ 个整数表示第 $i$ 只 Capoo 的体力值。（$1 \leq a_i \leq 10^9$）数据保证 $\sum n$ 之和不大于 $2 \times 10^5$ 。

Output

对于每组测试数据，输出一行一个整数表示答案，每两组数据之间的答案需换行。

Solving

使用单调栈配合进行反悔贪心即可，始终用序列中体力值最小且能兜住上层所有Capoo的Capoo作为底盘

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


void solve()
{       
    int n;
    cin >> n;
    vector<int> capoo(n+1);
    for(int i=1;i<=n;i++) cin >> capoo[i];
    int pre = 0;
    stack<int> stk;
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        while(!stk.empty() and capoo[i] < stk.top()) // 此时的底盘capoo大于这个capoo
        {
            if(pre - capoo[stk.top()]<= capoo[i]) // 并且用这个小底盘capoo依旧可以接住之前的capoo时就加入
            {
                pre -= capoo[stk.top()];
                stk.pop();
            }
            else break;
        }
        if(pre <= capoo[i])
        {
            stk.push(i);
            pre += capoo[i];
        }
    }
    cout << stk.size() << endl；// 栈中最后的状态就是答案序列
}