UVA 11572 题解
题目
题面
Emily the entrepreneur has a cool business idea: packaging and selling snow akes. She has devised a
machine that captures snow akes as they fall, and serializes them into a stream of snow akes that ow,
one by one, into a package. Once the package is full, it is closed and shipped to be sold.
The marketing motto for the company is \bags of uniqueness." To live up to the motto, every
snow ake in a package must be different from the others. Unfortunately, this is easier said than done,
because in reality, many of the snow akes owing through the machine are identical. Emily would like
to know the size of the largest possible package of unique snow akes that can be created. The machine
can start lling the package at any time, but once it starts, all snow akes owing from the machine
must go into the package until the package is completed and sealed. The package can be completed
and sealed before all of the snow akes have owed out of the machine.
Input
The rst line of input contains one integer specifying the number of test cases to follow. Each test
case begins with a line containing an integer
n
, the number of snow akes processed by the machine.
The following
n
lines each contain an integer (in the range 0 to 10
9
, inclusive) uniquely identifying a
snow ake. Two snow akes are identi ed by the same integer if and only if they are identical.
The input will contain no more than one million total snow akes.
Output
For each test case output a line containing single integer, the maximum number of unique snow akes
that can be in a package.
Sample Input
1
5
1
2
3
2
1
Sample Output
3
这里简单解释一下题意：
有 T 组输入数据，每组数据中有一个整数 n 以及一个 长度为n的数列。求在给定的数列中的最大的连续的没有重复元素的子数列。
其实这是一个很水的题，只需要实现一个简单的数据结构—-滑动窗口（或许简单地都不能称为数据结构）。
题解
思路
我们考虑到，每个合法的子数列都可以视作一个在数列上滑动的窗口，可以用start和size来记录个窗口，且主要有向后拓张以及向后缩两种操作。
- 向后拓张：在当前窗口的下一个元素合法的情况下，可以向后拓张，即将
size增加1 - 向后缩： 需要向后寻找挪动，但是当前窗口的下一个元素不合法，则需要将窗口的第一个元素删去，即
start增加1，size减少1。
通过这两种操作，即可实现窗口在数列上的滑动！
注意：元素的是否合法是根据具体题目来判断的
代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
vector<int> data;
int n;
struct arr
{
vector<int>& data;
int start;
int size;
int ans;
map<int,int> flag;
int& get_value(int c)
{
if(flag.find(c)==flag.end())
flag[c]=0;
return flag[c];
}
arr(vector<int>& vec):data(vec)
{
start=0;
size=0;
ans=0;
}
void run()
{
if(data.size()==0)
{
ans=0;
return;
}
size=1;
get_value(data[0])=1;
ans=max(ans,size);
while(start+size<data.size())
{
if(get_value(data[size+start])==0)
{
ans=max(ans,size+1);
get_value(data[size+start])+=1;
size+=1;
}
else
{
start+=1;
size-=1;
get_value(data[start-1])-=1;
}
}
}
};
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
data.clear();
data.resize(n);
for(int i=0;i<n;i++)
cin>>data[i];
arr container(data);
container.run();
cout<<container.ans<<endl;
}
return 0;
}
