AtCoder-abc407_e解析

时隔一年，我又来了！

题目链接

让我们一步一步详细分析这个问题：

1. 基本性质分析：

   • 题目给出的序列由n对括号组成，意味着总长度为2n
   • 根据括号匹配规则，序列首项必须是左括号'('，末尾必须是右括号')'
   • 因此我们可以确定第1项为'('，第2n项为')'，这是构建合法序列的基础

2. 构建策略：

   • 采用逐项构建的方法，每次考虑添加2个值（1对括号）
   • 对于中间的位置选择（第2到第2n-1项），需要保证：
     • 在任何前缀中，左括号数量≥右括号数量
     • 最终左括号总数等于右括号总数
   • 为了满足这些条件，可以使用贪心算法：
     • 维护当前可用的左括号和右括号数量
     • 每次选择时优先选当前可用的最大字符

3. 优化实现：

   • 直接排序每次可选字符的时间复杂度为O(n^2 logn)
   • 使用最大堆（优先队列）优化：
     • 初始化时将n-1个左括号和n-1个右括号放入堆中
     • 每次取出堆顶的最大元素作为当前选择
     • 选择后更新可用括号数量
   • 堆操作的时间复杂度为O(n logn)，显著优于排序方法

4. 具体步骤示例： a) 固定首位为'('，末位为')' b) 初始化最大堆：加入n-1个'(', n-1个')' c) 循环2n-2次： i. 取出堆顶元素 ii. 添加到序列中 iii. 更新剩余括号计数 d) 最后添加')'完成序列

5. 合法性验证：

   • 在整个构建过程中：
     • 始终保持左括号总数≥右括号总数
     • 最终两者数量相等
     • 堆的优先选择机制确保字典序最大

这种通过堆优化的贪心算法，既能保证生成合法括号序列，又能高效地得到字典序最大的结果。

上代码：

#include<bits/stdc++.h>
using namespace std;
long long t,n,a[400010];
int main(){cin>>t;while(t--){cin>>n;for(int i=1;i<=2*n;i++) cin>>a[i];long long sum=a[1];priority_queue<long long> h; for(int i=2;i<=2*n-1;i++){h.push(a[i]);i++;h.push(a[i]);sum+=h.top();h.pop();}cout<<sum<<endl;}return 0;
}

最后提醒一句：一定要开long long!!

求关注。