CodeForces - 899E Segments Removal (优先队列 + 链表)
2024-09-07 09:18:15
给定一个序列,每次从序列中找一个长度最大的元素相同的片段,删除它。
如果长度相同,删除最靠左边的那个片段。
问,需要删几次。
用链表处理删除片段。对于删除之后两边又能连成一个片段的那种情况,用set记一下合并就好了。
就是如果这个片段被合并成另一片段了,那么优先队列取到这个的时候就直接pop掉。
本来用自定义的结构体实现的。看了大佬的博客,学会了pair的妙用。
pair <a, b>若被排序, a是第一关键字,b是第二关键字。
#include <bits/stdc++.h>
using namespace std;
#define maxn 2000000 + 1000
typedef pair<int, int> Node;
int a[maxn], l[maxn], r[maxn];
int sum[maxn], num[maxn];
set<Node> flag;
priority_queue<Node> q; int main()
{
int n, tot = ;
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]); int tmp = ;
for (int i = ; i <= n; i++)
if (a[i] == a[i+]) tmp++;
else sum[++tot] = tmp, num[tot] = a[i], tmp = ; for (int i = ; i <= tot; i++)
l[i] = i-, r[i] = i+, q.push(Node(sum[i], -i)); int ans = ;
while(!q.empty())
{
int len = q.top().first, index = -q.top().second;
q.pop();
if (flag.count(Node(len, -index))) continue; ans++; int left = l[index], right = r[index];
if (left >= && right <= tot && num[left] == num[right])
{
flag.insert(Node(sum[left], -left));
flag.insert(Node(sum[right], -right));
sum[left] += sum[right];
q.push(Node(sum[left], -left)); r[left] = r[right];
l[r[right]] = left;
}
else
r[left] = right, l[right] = left;
} printf("%d\n", ans);
}
最新文章
- Android与H5交互(java与js的交互)
- MYSQL select查询练习题
- Android开发:第五日番外——过时的函数和被横杠的函数
- Xcode-Xcode 7.3 解决不能自动联想问题
- Android Contacts (android通讯录读取)-content provider
- <;a href=&#39;?out=login&#39;>;是什么意思
- LINQ 的查询_联表、分组、排序
- CentOS 7 for ARM 安装一键Lnmp失败
- 我与 windows kernel 的一段时光
- 实现Windows程序的数据绑定
- 15 Action View 以及监听 的使用
- 配置Https 和 HSTS
- Python 实现获取微信好友信息
- matplotlib中subplot的使用
- Fedora安装Snapd和Snap软件包
- ssh整合not found class 异常总结
- Jquery回到顶部功能
- 带你玩转Eclipse项目转成AndroidStudio项目
- iOS - 开源框架、项目和学习资料汇总(动画篇)
- c++builder XE6 Remote Debuger 远程调试