输入/输出优化¶

这种优化主要是针对某些数据量特别大的问题，比如数据到了 $10^7$ ，这就提示我们的算法必须是 $O(n)$ ，这个时候算法的常数就很重要，同时输入和输出的影响也会很大。

比如洛谷-P6033 合并果子加强版，这道题目在核心算法不变的情况下，使用scanf()和关闭同步的cin/cout都会在大数据的时候TLE，所以有必要学习一下针对整型数的快读和快写。

关闭同步¶

面对大数据输入时，如果使用C++的cin和cout，即使算法正确，也会造成TLE，这是因为在C++里，为了兼容C，保证使用printf和std::cout不发生混乱，将输出流绑定在了一起。解决的办法就是选择不兼容，于是使用std::ios_base::sync_with_stdio(false);，这样做的后果是不能同时使用std::cin/std::cout 和 scanf/printf。

解除绑定¶

C++在默认的情况下，std::cin和std::cout是绑定在一起的，函数tie是将两个stream绑定的函数，参数为空的化则解除绑定。C++默认在执行<<后都调用flush，会增加IO负担，可以通过cin.tie(NULL);和cout.tie(NULL);来加快输入和输出。

综上两步，在选择使用C++版本的cin和cout作为输入和输出的时候，要格外小心，最好在主函数开头这么写：

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    return 0;
}

`getchar()`加快读入¶

函数getchar()用来读取1 Byte的数据并转为char类型，速度比scanf()快很多，多以可以选择“读入字符 —> 转换为整型数”来代替输入。在头文件<cctype里提供了isdigit函数。

inline int read()
{
    int res = 0, sign = 1;
    char ch = 0;
    while (!isdigit(ch)) { //ch不是数字的时候
        if (ch == '-') sign = -1;
        ch = getchar(); //继续读入
    }

    while (isdigit(ch)) {
        res = res * 10 + (ch - '0');
        ch = getchar();
    }

    return res * sign; 
}

`putchar()`加快输出¶

putchar()用来输出单个字符，速度快于printf()。注意的是负数的负号要单独判断，并且利用取模取出的是末尾数字，需要倒序输出，一般选择用递归的方法去实现。但是递归的函数调用开销值得考虑，所以考虑手动实现一个栈。

inline void write(int x)
{
    static int myStack[35];
    int top = 0;
    do {
        myStack[top++] = x % 10;
        x /= 10;
    } while (x);

    while (top) putchar(myStack[--top] + '0');
}

更为通用的输入/输出优化¶

前面的是针对int类型来进行的优化，但是程序里long long也很常见，所以可以考虑使用C++的模板来实现针对所有整型的优化，也就是那个很霸气的名字“输入/输出外挂”。

template <typename T>
inline T read()
{
    T res = 0, sign = 1;
    char ch = 0;
    while (!isdigit(ch)) {
        if (ch == '-') sign = -1;
        ch = getchar();
    }

    while (isdigit(ch)) {
        res = res * 10 + (ch - '0');
        ch = getchar();
    }

    return res * sign;
}

template <typename T>
inline void write(T x)
{
    static int myStack[35];
    int top = 0;
    do {
        myStack[top++] = x % 10;
        x /= 10;
    } while (x);

    while (top) putchar(myStack[--top] + '0');
}

int main()
{
    int n = read<int>();
    long long a = read<long long>();
    write<long long>(a);
}

典型问题——各种优化¶