文章目录
- 最少连续页(poj3320)
- 分析题意
- 第一步:找第一个满足条件区间
- 第二步:开始将左端边界向右移,达到“缩小”区间、减少连续页的目的。
- 归纳总结代码
尺取法:顾名思义,像尺子一样取一段,借用挑战书上面的话说,尺取法通常是对数组保存一对下标,即所选取的区间的左右端点,然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多,尤其是数据量大的时候,所以说尺取法是一种高效的枚举区间的方法,是一种技巧,一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方,有些情况下尺取法不可行,无法得出正确答案,所以要先判断是否可以使用尺取法再进行计算。
本人为一名普通二本学校自动化专业的大二学生,对编程有着少许兴趣。
最近想了解什么是尺取法,于是想写道简单尺取法相关的题目,当练一练手。
最少连续页(poj3320)
题意:一本书有P页,每一页都一个知识点,求去最少的连续页数覆盖所有的知识点。
样例
输入:
6
1 1 3 1 2 3
输出:
3
备注:一本书有6页,第一页知识点为1…第6页知识点为3。
分析题意
按照尺取法的定义:一种高效的枚举区间的方法。我们应该先在找一个满足条件的区间(不一定是最优),然后再通过将左边界向右移、右边界向右移的方式需找最优区间。
第一步:找第一个满足条件区间
为了能够更好地找到最优区间,我们需要先了解有多少个不同的知识点、在已读的页数中每个知识点出现了几次。
map <int, int> cnt;
set <int> t;
①:可以用set容器“不能重复插入”的特性,统计书中出一共有多少个不同的知识点。
for (int i = 0; i < p; i++)
{
scanf("%d", &a[i]);
t.insert(a[i]);
}
int num = t.size();
插入个数 num=3
②:可以用map容器“映射”的特性,统计出在已读的页数中相同知识点出现次数。
while (end<p && sum<num)
{
if (cnt[a[end]] == 0)
sum++;
cnt[a[end]]++;
end++;
}
第二步:开始将左端边界向右移,达到“缩小”区间、减少连续页的目的。
begin:左边界下标 end:右边界下标
ans:当前已读最少连续页
在满足条件的区间里
如果右边界下标减去左边界下标小于当前已读最少连续页。
那么右边界下标减去左边界下标就是当前最少页数。
如果end-begin<ans,则ans=end-begin+1。
初始状态(第一个满足条件区间)
当前状态:begin=0 end=4 ans=5
当a[0]知识点在已读页数出现过,则将左边界向右移,右边界不变。
当前状态:begin=1 end=4 ans=4
当a[1]知识点在已读页数出现过,左边界向右移,右边界不变。
当前状态:begin=2 end=4 ans=3
当a[2]知识点在已读页数未出现过,右边界要向右移,找到满足条件的区间。
当前状态:begin=3 end=4 ans=3
当前状态:begin=1 end=5 ans=3
右边界找到合适位置后,左边界再向右移。
此时a[3]知识点在已读页数未出现过,右边界要向右移,找到满足条件的区间。可是右边界已经到达最后一页,结束查找。
最终得到最少页数为3。
while (1)
{
while (end<p && sum<num)
{
if (cnt[a[end]] == 0)
sum++;
cnt[a[end]]++;
end++;
}
if (end==p) break;
if(ans>end-begin)
ans = end-begin;
cnt[a[begin]]--;
if(cnt[a[begin]]==0)
sum--;
begin++;
}
归纳总结代码
通俗版
#include <bits/stdc++.h>
#include<algorithm>
#include <set>
#include <map>
#define MAX 1000010
#define ll long long
#define INF 1000010
using namespace std;
int a[MAX];
map <int, int> cnt;
set <int> t;
int main()
{
int p, ans = INF, begin=0, end=0, sum=0;
scanf("%d", &p);
for (int i = 0; i < p; i++)
{
scanf("%d", &a[i]);
t.insert(a[i]);
}
int num = t.size();
while (1)
{
while (end<p && sum<num)
{
if (cnt[a[end]] == 0)
sum++;
cnt[a[end]]++;
end++;
}
if (end==p) break;
if(ans>end-begin)
ans = end-begin;
cnt[a[begin]]--;
if(cnt[a[begin]]==0)
sum--;
begin++;
}
cout<<ans<<endl;
return 0;
}
精简版(来源网上)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define MAX 1000010
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int a[MAX];
map <int, int> cnt;
set <int> t;
int p, ans = INF, st, en, sum;
int main()
{
scanf("%d", &p);
for (int i = 0; i < p; i++) scanf("%d", a+i), t.insert(a[i]);
int num = t.size();
while (1){
while (en<p && sum<num)
if (cnt[a[en++]]++ == 0) sum++;
if (sum < num) break;
ans = min(ans, en-st);
if (--cnt[a[st++]] == 0) sum--;
}
printf("%d\n", ans);
return 0;
}
希望能够将自己的一些学习经验分享给有需要的人。
我是小郑,一个坚持不懈的小白。
博客参考链接
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)