当前位置: 首页 > news >正文

CF45C Dancing Lessons 题解

CF45C Dancing Lessons 题解

不就是洛谷的 P1878 吗,雾。

暴力的时间复杂度是 \(O(n^2)\) 的,考虑优化。

考虑使用优先队列。内部存三个元素:绝对值、左边的孩子、右边的孩子。

这样我们重载运算符可以以绝对值为第一关键字,左边的孩子为第二关键字进行排序。

然后我们每次抽出来的一对小朋友他们的左边和右边都是有可能对答案产生贡献的,所以可以用链表进行维护。

最后还要判个重,这个打个标记即可。

还有不懂的就看代码吧。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N];
bool kd[N],vis[N];
vector<pair<int,int> > ans;
struct LIST{int l,r;
}lst[N];
struct NODE{int val,l,r;bool operator < (const NODE &x)const{if(val!=x.val)return x.val<val;if(l!=x.l)return x.l<l;return x.r<r;}
};
priority_queue<NODE> pq;
int main(){ios::sync_with_stdio(0);cin>>n;for(int i=1;i<=n;++i){char ch;cin>>ch;if(ch=='B')kd[i]=1;}for(int i=1;i<=n;++i)cin>>a[i];for(int i=1;i<=n;++i)//初始化链表lst[i].l=i-1,lst[i].r=i+1;
//	lst[1].l=n;lst[n].r=1;
//	for(int i=lst[0].r;i;i=lst[i].r)cout<<lst[i].uid<<' ';
//	cout<<'\n';for(int i=1;i<n;++i)if(kd[i]!=kd[i+1])pq.push((NODE){abs(a[i]-a[i+1]),i,i+1});//初始值while(!pq.empty()){int l=pq.top().l,r=pq.top().r;pq.pop();if(vis[l]||vis[r])continue;ans.push_back(make_pair(l,r));vis[l]=vis[r]=1;lst[lst[l].l].r=lst[r].r;lst[lst[r].r].l=lst[l].l;int x=lst[l].l,y=lst[r].r;if(x<1||x>n||y<1||y>n)continue;//在链表中,1的左边是0,n的左边是n+1,不合法if(kd[x]!=kd[y]){if(x<=y)pq.push((NODE){abs(a[x]-a[y]),x,y});elsepq.push((NODE){abs(a[x]-a[y]),y,x});}}	cout<<(int)ans.size()<<'\n';for(int i=0;i<(int)ans.size();++i)cout<<ans[i].first<<' '<<ans[i].second<<'\n';return 0;
}

AC 记录。

http://www.hskmm.com/?act=detail&tid=27632

相关文章:

  • APUE学习笔记之文件IO(三) - Invinc
  • note
  • 供应链优化技术助力应对疫情挑战
  • 搜索关键词 - 呓语
  • 阅读《构建之法》产生的问题
  • 每日反思
  • 每日反思(2025.10.09)
  • 软件工程学习日志2025.10.9
  • 骄傲 雨伞边缘处的暗槽 从最原初裂缝开凿 被碰触和温暖击倒 停止思考
  • 1.1.1.2 直接融资vs间接融资的区别
  • 柳高国庆小小说创作比赛的构思和成文(未完成)
  • 骄傲 孔雀羽翎上的暗槽 从最肮脏裂缝开凿 被爱意和现实击倒 停止创造
  • 10.9 CSP-S模拟28 改题记录
  • 所以相信我初登场 不会让任何人失望 无论地位不管成败 全都逃不出神的覆掌
  • 被彼此笼罩 任歌声将我们缠绕 立下誓言后再自嘲 重复仲夏夜的舞蹈 吞下这毒药
  • 朝圣显像 不及那人将门扉轻轻叩响 欢迎来到我的城市 嗅玫瑰绽放
  • Git克隆项目运行指南
  • webpack library - 指南
  • 2025.10.9 月考游寄 - Amy
  • 被彼此笼罩 任回忆将我们缠绕 狂欢者戴上了镣铐 得益者撕裂了嘴角 吞下这毒药
  • QGIS导出TIF栅格图层
  • 七层协议
  • 20251009
  • 单调栈
  • 各种B站客户端
  • 10.9正式恢复
  • CSP-S模拟27
  • 模型训练技巧 - -一叶知秋
  • 20232324 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 2025.10.8 训练记录