题目大意:Jessica期末考试临时抱佛脚想读一本书把知识点掌握,但是知识点很多,而且很多都是重复的,她想读最少的连续的页数把知识点全部掌握(知识点都在书上,每一页都是一个知识点)
这一题可以用3061的游标卡尺法,我们可以先数数书上倒到底有多少个知识点,因为知识点都是序数,我们可以用二分法直接找到O(PlogP),这里可以采用set模板直接偷懒了,然后我们就可以用游标卡尺法了,因为所有知识点都要出现一次,所以我们统计新的知识点的出现就好了,最后我们找最短的那个连续就好。
#include <iostream>
#include <functional>
#include <algorithm>
#include <map>
#include <set> using namespace std; static int books[]; void solve(const int); int main(void)
{
int pages;
while (~scanf("%d", &pages))
{
for (int i = ; i < pages; i++)
scanf("%d", &books[i]);
solve(pages);
}
return ;
} void solve(const int pages)
{
int ideas_size, s = , t = , ans, nums = ;//游标卡尺法标准形式
static set<int>ideas;
static map<int, int>index;//把ideas和index放函数里面初始化能省几十ms for (int i = ; i < pages; i++)
ideas.insert(books[i]);
ideas_size = ideas.size();
ans = pages;//ans千万不要初始化成答案个数了,之前在这里初始化错了导致wa while ()
{
while (t < pages && nums < ideas_size)
{
if (index[books[t++]]++ == )//找不到这个元素,则一定在尾端
nums++;
}
if (nums < ideas_size)//因为知识点的个数一定是符合条件的,所以这里直接作为跳出条件就可以了
break;
ans = min(ans, t - s);
if (--index[books[s++]] == )
nums--;
}
printf("%d\n", ans);
}
因为使用模板的,所以速度会慢一点