【题解】Ithea Plays With Chtholly codeforces – 897D —quhengyi11

传送门:D.Ithea Plays With Chtholly

题意：$Chtholly$要在长度为 $n$的空序列中填数，进行 $m$个回合，$Ithea$每个回合会给 $Chtholly$一个在 $1$到 $c$之间的数，$Chtholly$可以用这个数填入这个序列里的一个空位置里，也可以填入这个序列里一个有数字的位置，将这个位置原来的数字变为当前的这个数字，$Chtholly$能赢当且仅当序列里没有空位置且序列里的数是不下降的 (即 $\forall i\;a_i<=a_{i+1}$)，如果 $m$回合后 $Chtholly$没赢就是 $Ithea$赢，我们保证 $Chtholly$能赢，现在请你帮 $Chtholly$赢得这场比赛。

数据范围：$n,m\geq 2,1\leq c\leq 1000,1\leq n\times \lceil \frac c 2\rceil \leq m \leq 1000$

吐槽：珂朵莉都进驻 codeforces 了 QAQ 我还没看这番，主要是 bilibili 没有（其实是我懒得去找百度云），有时间就去追一下 233333

因为 $APIO$里有一堆交互题，所以我就去做了几道交互题练练手。这道算是比较难的一道。

首先一个平凡的想法是把序列初值设成 $\infty$，每次从左到右选第一个比当前拿到的数大的数，这就相当于维护了序列的不下降性。

但是如果要填充完整个序列，不难想到最坏情况下需要进行 $(n-1)\times c+1$个回合，比如下面这个例子：

$n=3,c=4$

给你是数分别是 $4,3,2,1,4,3,2,1,4$，用上面那个方法则需要 $9$轮，而 $m$的下界是 $6$，因此这种方法是不对的。

那咋整呀？

首先我们看一看第一种算法的运行过程，回合主要浪费在了重复覆盖同一个位置，由数据范围可以知道，如果我们对于一个位置的覆盖次数的上界能够控制在 $\lceil \frac c 2\rceil$处，我们就能够在大于等于上界的 $m$轮次内完成这个合法序列。

可是我还是不会呀 (委屈脸.jpg)

Q: 看到这个 $\lceil \frac c 2\rceil$你想到了什么？

A: 啥都没想到。

Q:(小声) 快给我说二分。

A: 二分！

Q: 看吧你会做了吧！

A: 黑人问号？？？

我们可以把值域分为两部分，小于等于 $\lceil \frac c 2\rceil$的从左往右填找第一个比自己大的数，大于 $\lceil \frac c 2\rceil$的从右往左填找第一个比自己小的数，随便加点细节处理乱搞可过。

为啥？

因为填充一个格子次数的上界是 $\lceil \frac c 2\rceil$呀~

这个思路真是超级好玩~

具体如果没看明白或者不知道怎么加细节处理的可以看看代码。

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define N 1005
int n, m, c, a, f[N], mid, cnt, j, g[N];
int main ()
{
    scanf("%d %d %d", &n, &m, &c);
    memset(f, 0x3f, sizeof f);
    memset(g, 0, sizeof g);
    mid = c / 2;
    fo (i, 1, m)
    {
        scanf("%d", &a);
        if (a <= mid)
        {
            j = 1;
            while (f[j] <= a && j <= n) j++;
            if (f[j] == f[0])
                ++cnt;
            f[j] = a;
            g[j] = a;
            printf("%d\n", j);
        }
        else
        {
            j = n;
            while (g[j] >= a && j >= 1) j--;
            if (g[j] == 0)
                ++cnt;
            f[j] = a;
            g[j] = a;
            printf("%d\n", j);
        }
        fflush(stdout);
        if (cnt == n)
            return 0;
    }
    return 0;
}

作为一个 windows 玩家做交互题太累了，魔改 grader.cpp 之后才能本地测试 QAQ，不过听说 APIO 是 linux 系统所以大概可以直接用命令行啦~，好吧我得快点转 linux 了