【t011】最小覆盖子串
2024-09-08 10:21:47
Time Limit: 1 second
Memory Limit: 32 MB
【问题描述】
给定一个含有N个元素的序列A,你的任务就是求出序列A的最小覆盖子串的长度。
本题中的一些定义:
串S,是由零个或多个元素组成的序列,其下标从1开始计数。Si 表示串 S 中第 i 个位置的元素值,串的长度N指的是串中元素的个数。
串中任意连续(非空)个元素组成的序列称为该串的子串。子串可以表示成S’:Si,…,Sj,1≤i≤j≤N。
如果子串 S’ 中的不同元素值个数与原串 S 中的不同元素值个数相同,我们称子串 S’ 为原串 S 的覆盖子串,长度最小的覆盖子串称之为原串的最小覆盖子串,我们的任务就是求出最小覆盖子串的长度。
【输入格式】
输入数据的第一行为一个整数N,表示序列中有N个整数(1≤ N ≤1,000,000),序列中不同元素值的个数不超过100,000。第二行有N个整数A1,…,An。
0≤ Ai ≤ 1,000,000,000 1≤i≤N
【输出格式】
输出一行一个整数L,表示给定序列的最小覆盖子串的长度。
【输入样例1】
5
1 8 8 8 1
【输出样例1】
2
【输入样例2】
11
5 1 5 3 2 6 3 8 4 2 5
【输出样例2】
8
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t011
【题意】
【题解】
/*
维护一个队列;
先把第一个元素加入队列;
对于新读入的元素;
看看是不是和头节点相同;
如果和头节点相同
则把头结点去掉;
然后头结点指向下一个值;
然后如果该值在这个队列中出现了多次;>1
则继续递增头结点;
如果队列中不同的元素个数和原序列相同了就尝试更新答案;
*/
【完整代码】
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 1e6+100;
int a[N],n,head,tail,tot,dl[N],now ,ans;
map <int, int> dic1,dic2;
void in()
{
rei(n);
rep1(i, 1, n)
{
rei(a[i]);
if (!dic1[a[i]])
{
dic1[a[i]] = 1;
tot++;
}
}
}
void ga()
{
ans = N;
head = tail = 1;
dic2[a[1]] = 1,dl[1] = a[1];
now = 1;
if (now == tot)
ans = min(ans, 1);
rep1(i, 2, n)
{
dl[++tail] = a[i];
if (!dic2[a[i]])
{
dic2[a[i]] = 1;
now++;
}
else
dic2[a[i]]++;
while (dic2[dl[head]] > 1)
{
dic2[dl[head]]--;
head++;
}
if (now == tot)
{
ans = min(ans, tail - head + 1);
}
}
}
void out()
{
printf("%d\n", ans);
}
int main()
{
//freopen("F:\\rush.txt", "r", stdin);
in();
ga();
out();
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
最新文章
- jQuery Scroll Follow
- jsnop
- 2015第42周六Pgsql全文索引
- 求实现sql?
- 【Matlab编程】Matlab让电脑失而复得
- AR_Demon(使用vuforia平台提供的钥匙跟后台,实现相机拍图片读取模型以及视频的功能)
- JQuery 相关用法和操作
- kendo ui grid选中行事件,获取combobox选择的值
- python库termcolor用法
- BlackArch安装(译文)
- 第四周WordCount优化
- Oracle 执行计划(二)------表访问的几种方式
- 解决git pull/push每次都需要输入密码问题 和 HttpRequestException encountered
- The Non-Inverting Amplifier Output Resistance by Adrian S. Nastase [转载]
- js中各种弹窗
- StringDemo
- NFS服务端与客户端配置
- Activex打包于发布完整版---ActiveX打包
- js定义一个处理字符串的函数
- python中访问限制
热门文章
- 【BZOJ 1146】【CTSC 2008】网络管理network
- Android 软键盘弹出,界面整体上移的问题
- less相关知识点
- JS版微信6.0分享接口用法分析
- ehcache、memcache、redis三大缓存比较(转)
- 面向对象的CSS
- VMware linux虚拟机在线识别新添加磁盘
- [Flexbox] Use Flex to Scale Background Image
- MySQL—Install/Remove of the Service Denied
- 公钥,私钥和数字签名这样最好理解 分类: B3_LINUX 2015-05-06 16:25 59人阅读 评论(0) 收藏