Colorful Candies 题解 (at_abc210 C map离散化 滑动窗口)
2021/7/22 23:14:17
本文主要是介绍Colorful Candies 题解 (at_abc210 C map离散化 滑动窗口),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Colorful Candies 题解 [at_abc210 C map离散化 滑动窗口]
- 题目:Colorful Candies
- 解析
- 参考源码
题目:Colorful Candies
地址:at_abc210_c
解析
-
TAG: map离散化 滑动窗口
-
DESCRIPITION:
有一排不同色地蜡烛问你连续一个K大小地区间内有多少种颜色。 -
INPUT:
-
SOLUTION:
颜色很多,我们用map来记录当下颜色是否存在,然后简单的从左向右滑动窗口,减去离开窗口地颜色,加上进入窗口的颜色,同时更新颜色数量的最大值。反正很简单直接上代码:
参考源码
/* 其实我感觉这道题最大的意义还是熟悉了下map的使用(虽然这么说牵强了点) 比如说 m.erase()来移除键值对, m.count() 判断是否有键出现。 */ #include<iostream> #include<string> #include<map> using namespace std; const int MAXN = 3e5; map<int,int> m; int nums[MAXN+10]; int c[MAXN+10]; int main() { int N,K; //choose K consecutive candies // i [1,N-K+1] cin>>N>>K; nums[N-K+1] = 0; int ns = 0; int maxx = 0; for(int i=1;i<=N;i++){ cin>>c[i]; // 接下来对前K个蜡烛的颜色情况做个特殊处理方便接下来直接从K+1开始滑动窗口 if(i<=K){ if(m.count(c[i])==0){ m[c[i]]=1; ns++; //nums[N-K+1]++; } else{ m[c[i]]++; } } } maxx = ns; for(int i=K+1;i<=N;i++){ m[c[i-K]]--; // 旧的蜡烛滑出一个 if(m[c[i-K]]==0){ // 这个颜色数量归零,去掉这个map映射 ns--; m.erase(c[i-K]); } if(m.count(c[i])==0){ // 新的蜡烛滑入一个,并且这个颜色没有出现过,更新新map和答案最大值 m[c[i]]=1; ns++; if(ns>maxx) maxx = ns; // 只有出现新的颜色才有可能更新最大值 } else{ // 新的蜡烛滑入一个,并且这个颜色出现过,直接该颜色数量+1 m[c[i]]++; } } cout<<maxx<<endl; return 0; }
这篇关于Colorful Candies 题解 (at_abc210 C map离散化 滑动窗口)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验