给定一个序列,每次从序列中找一个长度最大的元素相同的片段,删除它。

如果长度相同,删除最靠左边的那个片段。

问,需要删几次。

用链表处理删除片段。对于删除之后两边又能连成一个片段的那种情况,用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);
}

最新文章

  1. Android与H5交互(java与js的交互)
  2. MYSQL select查询练习题
  3. Android开发:第五日番外——过时的函数和被横杠的函数
  4. Xcode-Xcode 7.3 解决不能自动联想问题
  5. Android Contacts (android通讯录读取)-content provider
  6. &lt;a href=&#39;?out=login&#39;&gt;是什么意思
  7. LINQ 的查询_联表、分组、排序
  8. CentOS 7 for ARM 安装一键Lnmp失败
  9. 我与 windows kernel 的一段时光
  10. 实现Windows程序的数据绑定
  11. 15 Action View 以及监听 的使用
  12. 配置Https 和 HSTS
  13. Python 实现获取微信好友信息
  14. matplotlib中subplot的使用
  15. Fedora安装Snapd和Snap软件包
  16. ssh整合not found class 异常总结
  17. Jquery回到顶部功能
  18. 带你玩转Eclipse项目转成AndroidStudio项目
  19. iOS - 开源框架、项目和学习资料汇总(动画篇)
  20. c++builder XE6 Remote Debuger 远程调试

热门文章

  1. C# 连接oracle,用32位client和64位Client,可能导致结果不同
  2. Main函数中的参数argc,argv的使用简单解析
  3. CQRS之旅——旅程4(扩展和增强订单和注册限界上下文)
  4. centos6.3搭建FTP服务器图文教程
  5. C#数据类型 值传递和引用传递
  6. c#基础 path 类的各种套路
  7. VC++堆栈大小设置
  8. 编写C#程序,自动将bing首页图片设为壁纸
  9. MovieReview—Black Panther(黑豹)
  10. MyLinkedList