CSDN算法技能树-蓝桥杯基础-日志记录,是我学算法技能树的第一个卡点,然后我去百度尺取法,把它给做出来了,可是呢,百度又给出另一道类似题目,POJ3320杰西卡有毛病!下面展示我的问题:
我的源码:https://paste.ubuntu.com/p/pN92ym2Cy3/
题目地址:http://poj.org/problem?id=3320
为什么Runtime Error呢!!!讨论区太冷清了,给不了什么建设建议,而我按讨论区说的,没用cin(说是会超时),没用STL库(说是过不了,比如sort()和min()),然后我的代码中,题目测试样例 + 讨论区5组测试数据 + 自己编的5组测试数据,都能过,就是提交过不了????why, 求大佬解答, 会采纳
运行时错误,而不是结果出错,可能是下标越界,当a[j]>=N时,会发生下标越界,也有可能是申请的数组过大。
我尝试写了一个类,用于替代b[N]这个数组,但是超时了。
我的代码:
#include<cstdio>
#include<list>
#include<vector>
typedef struct {
int num;
int index;
} mint;
mint m;
class mintlist {
private:
std::list<mint>list;
int lastindex;
public:
mintlist(){
lastindex=-1;
}
int& operator [](int index) {
static std::list<mint>::iterator it;
if (index == lastindex) {
return it->num;
} else {
m.num = 0;
m.index = index;
if (list.empty()) {
list.push_back(m);
it = list.begin();
} else {
for (it = list.begin(); it->index < index && it != list.end(); it++);
if (it->index != index) {
it = list.insert(it, m);
}
}
lastindex = index;
return it->num;
}
}
void reset() {
std::list<mint>::iterator it;
for (it = list.begin(); it != list.end(); it++) {
it->num = 0;
}
}
};
int main() {
int n, num = 0, cnt = 0, ans;
scanf("%d", &n);
std::vector<unsigned int> a(n);
mintlist b;
ans = n;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
if (b[a[i]] == 0) {
num++;
b[a[i]] = 1;
} //得到不重复元素个数num
}
if (num < n) {
b.reset();
for (int i = 0, j = 0; i < n; ++i) {
if (b[a[i]] == 0) //a[i]原来不在区间内
cnt += 1; //区间内不重复元素个数
b[a[i]]++; //区间内a[i]个数
while (cnt == num) { //区间包括所有内容,这里不用if
if (ans > i - j + 1) ans = i - j + 1;
b[a[j]]--;
if (b[a[j]] == 0) cnt--;
j++; //左边界右移, j++记得放最后!!!
}
}
}
printf("%d", ans);
return 0;
}