Codeforces 1430C: Numbers on Whiteboard

Codeforces 1430C C++ 一解.

分析

白板上的数字初始状态是固定的 $1,2,\cdots,n$. 每次操作都会 “折损” 当下所有数字之和, 而 “折损” 的量即为选定的两个数之和的一半. 因此为使最后得到的数字最小, 一种贪心的方法是每次选择最大的两个数字做操作.

操作时对于两数之和为奇数的, 得到的新数字需要向上取整. 虽然有 “凭空” 增大数字总和的可能性, 但经过数学归纳即可得知最后一次操作选定的数字一定是 $1$ 和 $3$ $(n>2)$ 或 $1$ 和 $2$ $(n=2)$, 也即最后得到的数字为 $2$. 显然若要得到小于 $2$ 的数字, 需要在倒数第二次操作时白板上只剩下两个 $1$, 而这在向上取整的规则下是做不到的. 因此这种贪心方法即为最优解.

空间和时间优化

因为白板数字的初始状态是规律性的连续自然数列, 选定数字的过程也极为规律, 无需要实际使用栈等数据结构模拟. 官方题解则提供了使用实际数据结构 vector<int> 的方法.

代码

#include <iostream>

using namespace std;

void solveAndPrint(int n)
{
    cout << 2 << endl;
    cout << n - 1 << ' ' << n << endl;
    for (int i = 2; i < n; ++i)
    {
        cout << n - i << ' ' << n - i + 2 << endl;
    }
}

int main()
{
    int t, n;

    cin >> t;
    while (t--)
    {
        cin >> n;
        solveAndPrint(n);
    }

    return 0;
}