Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 不用STL就容易过,不用担心超时

Posted by a280920481 at 2018-11-02 00:25:09 on Problem 3320
```#include <iostream>
using namespace std;

int a[1000002];//先用来构建堆,再用来表示当前某个元素的数量

int b[1000002];//出现过的数的升序排列
int c[1000002];//原始数据
int np = 0;//不同数的种数

//堆的实现
void mypush(int x);
void mypop();
int hs = 0;

//二分查找某个数在b中的位置
int bs(int x);

int main()
{
int n;
int m;
scanf_s("%d", &n);

for (int i = 0; i < n; i++)
{
scanf_s("%d", &m);
c[i] = m;
mypush(m);
}

b[0] = a[0];
for (int i = 0; i < n; i++)
{
m = a[0];
mypop();
if (m != b[np])
{
np++;
b[np] = m;
}
}
np++;
for (int i = 0; i <= np; i++)
{
a[i] = 0;
}

int bp = 0, ep = 0;
int num = 0;

while (num < np)//先把所有元素囊括
{
if (a[bs(c[ep])]++ == 0)
{
num++;
}
ep++;
}
ep--;
int ans = ep;//先把最小值定为最初囊括所有元素的长度

while (true)
{
m = c[bp];
bp++;
if ((--a[bs(m)]) <= 0)
{
ep++;
while ((c[ep] != m) && (ep < n))
{
a[bs(c[ep])]++;
ep++;
}
if (ep == n)
{
break;
}
else
{
a[bs(m)]++;
}
}
if ((ep - bp) < ans)
{
ans = ep - bp;
}
}

printf_s("%d\n", ans + 1);//ans之前一直表示为最终答案减1

return 0;
}

void mypush(int x)
{
int me, fa, m;
me = hs;
hs++;
a[me] = x;

while (me)
{
fa = (me - 1) / 2;

if (a[fa] > a[me])
{
m = a[fa];
a[fa] = a[me];
a[me] = m;
}
else
{
break;
}
me = fa;
}

return;
}

void mypop()
{

hs--;
a[0] = a[hs];
int me = 0, son, m;

while (2 * me + 1 < hs)
{
son = 2 * me + 1;

if ((a[son] > a[son + 1]) && (son + 1 < hs))
{
son++;
}
if (a[me] > a[son])
{
m = a[me];
a[me] = a[son];
a[son] = m;
}
else
{
break;
}
me = son;
}

return;
}

int bs(int x)
{
int lp = -1, rp = np, mid;

while (rp - lp > 1)
{
mid = (lp + rp) / 2;

if (b[mid] < x)
{
lp = mid;
}
else
{
rp = mid;
}
}

return rp;
}
```

Followed by: