极端数据

一句话理解

极端数据是规模顶格、或专门卡你算法的数据。

为什么要学

本地过小样例，提交却 TLE/WA，常常是极端数据。

讲解

题目给了 n≤1e5，你就要用 1e5 量级想时间。给了 a_i 到 1e9，你就要想会不会爆 int。

极端不一定是最大。全 0、严格递减、完全相同，也可能打到你的漏洞。

自己造一组最大数据跑一下，至少能发现超时和溢出。

例子

int n = 100000;
long long sum = 0;
for (int i = 0; i < n; i++) sum += 1000000000LL;

十万个 1e9 加起来是 1e14，int 装不下。极端数据把溢出暴露出来。

常见错误

• 只用题目样例测试。
• 造极端数据时忘记看清题目范围。