5ab_juruo @ 2023-01-05 16:55:44
前情提要:https://www.luogu.com.cn/discuss/show?postid=553164
我以下面这段代码测试,注意被注释的那一行:
#include <cstdio>
using namespace std;
const int max_n = 100000;
int dp[max_n+1] = {-2147483648}, arr[max_n], ans = 1;
int ser(int low)
{
int l = 0, r = ans + 1, mid, ret;
while (l < r)
{
mid = (l + r) >> 1;
if (dp[mid] < low)
ret = mid, l = mid + 1;
else
r = mid;
}
return ret + 1;
}
int main()
{
int n, pos;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", arr + i);
dp[1] = arr[0];
for (int i = 1; i < n; i++)
{
// if (arr[i] >= dp[ans])
if (arr[i] > dp[ans])
{
dp[++ans] = arr[i];
continue;
}
pos = ser(arr[i]);
dp[pos] = arr[i];
if (pos > ans)
ans++;
}
printf("%d\n", ans);
return 0;
}
显然,被注释的部分是错误的,可以被下面这组数据卡掉:
6
1 1 1 1 1 1
正确的输出是
然后改成被注释的部分能过,实在是离了个大谱。
已经有人反馈过这个问题了:https://www.luogu.com.cn/discuss/show?postid=518643
by lfxxx @ 2023-01-05 16:56:51
B
开头的题目,应该不会加强数据。。。
by Feng_Jing @ 2023-01-05 17:00:54
addd
by fjy666 @ 2023-01-05 17:03:21
荔枝,你让我怎么荔枝?????
by __Dinic__ @ 2023-01-05 17:11:40
建议把标题改为树枝
by SDqwq @ 2023-01-05 17:16:44
荔枝,你让我怎么荔枝
by 5ab_juruo @ 2023-01-05 20:38:47
@chen_zhe
by Baoqiancheng11 @ 2023-07-10 16:30:13
有素质 ——小粉兔