Educational Codeforces Round 96 (Rated for Div. 2) 解题报告

CF1430C Numbers on Whiteboard

Educational Codeforces Round 96 第三题,构造题。

题目链接

题意翻译

  • 多组数据,数据组数为 \( t \);
  • 一开始有 \( n \) 个数,分别为 \( 1 , 2 , 3 , \cdots , n – 1 , n \)。
  • 每次选择两个数 \( a , b \),然后删除这两个数并把 \( \left\lceil \frac { a + b } { 2 } \right\rceil \) 插入到原序列;
  • 经过 \( n – 1 \) 次操作后,使得剩下的那一个数最小;
  • 要求你输出得到的最小值以及每次的操作方案;
  • 数据范围:\( 1 \leq t \leq 10 ^ 3 \),\( 2 \leq n \leq 2 \cdot 10 ^ 5 \),\( \sum n \leq 2 \cdot 10 ^ 5 \)。

题解

显然这道题需要我们构造出一种万能的方案,使得每次剩下的数字为 \( 2 \),这样才能得到最小。

我们不妨贪心考虑,如果每次都向上取整,那么答案有可能会因此增大。所以向上取整的数量要尽可能少,即奇偶性不同的合并要尽可能少。

另外考虑到平均数的性质,越大的数越应该先合并,这样答案才能最优。

综合上面的思考,我们不难构造出一种方案:

  • 答案为 \( 2 \);
  • 先把 \( n \) 和 \( n – 1 \) 合并,这里需要向上取整,得到 \( n \);
  • 然后合并 \( n \) 与 \( n – 2 \),得到 \( n – 1 \);
  • \( n – 1 \) 与 \( n – 3 \) 合并为 \( n – 2 \);
  • 一直合并下去,直到最后合并 \( 3 \) 与 \( 1 \),最后答案为 \( 2 \)。
#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg char ch = getchar();
    reg int res = 0;
    while (ch < '0' || '9' < ch)
        ch = getchar();
    while ('0' <= ch && ch <= '9')
        res = 10 * res + ch - '0', ch = getchar();
    return res;
}

int n;

int main(void)
{
    reg int t = read(); //读入数据组数
    while (t--)
    {
        n = read();                  //读入 n
        puts("2");                   //输出答案
        printf("%d %d\n", n - 1, n); //第一步特殊考虑
        for (reg int i = n; i > 2; --i)
            printf("%d %d\n", i - 2, i); //后面每一步都是这样
    }
    return 0;
}
Pages: 1 2 3 4 5 6 7 8 9