题解 CF896B 【Ithea Plays With Chtholly】

囧仙

2020-08-12 00:35:39

Solution

## 题目大意 有 $n$ 张卡纸,初始为空。现在有 $m$ 次操作,每次给一个 $[1,c]$ 内的正整数 $a_i$ ,要求将其写在某张卡纸上并覆盖原来的内容,使得 $m$ 次操作内,写在卡纸上的数从 $1$ 到 $n$ 非严格单调递增。 保证 $m\ge n\times \left\lceil\dfrac{c}{2}\right\rceil$ 。 ## 题解 挺有意思的一道交互题。考虑到截至这篇题解并没有构造方法的证明,这里先给出构造方法,再给出证明。 **构造方法**:如果 $a_i\le \left\lfloor\dfrac{c}{2}\right\rfloor$ ,就从左往右找到第一个大于 $a_i$ 或空的卡纸填入;否则从右往左找到第一个小于 $a_i$ 或空的卡纸填入。 **证明**:先考虑一个小问题:如果有 $m_0$ 次, $c_0$ 种的操作,用这种方法从左往右填,可以保证多少格非严格单调递增? 考虑出现次数最多的操作。显然,所有操作出现次数的平均值为 $\dfrac{m_0}{c_0}$ ,因而最大值必定不小于平均值。也就是说,出现次数最多的操作至少出现了 $\left\lceil\dfrac{m_0}{c_0}\right\rceil$ 次,不妨设这种操作的数字为 $x$ 。考虑这 $m_0$ 次填充,显然小于 $x$ 的操作不会影响到已经形成的非严格单调递增序列,而 $x$ 会忽略所有大于 $x$ 的操作。因而,可以保证这个非严格单调队列的长度不小于 $\left\lceil\dfrac{m_0}{c_0}\right\rceil$ 。 现在我们的构造方案分成了两段。不妨设不超过 $\left\lfloor\dfrac{c}{2}\right\rfloor$ 的操作共有 $t$ 个,则超过的共有 $m-t$ 个。由刚刚证明的结论,两部分拼成的非严格单调递增序列的长度: $$\left\lceil\dfrac{2\times t}{c}\right\rceil+\left\lceil\dfrac{2\times (m-t)}{c}\right\rceil\ge \frac{2\times m}{c} \ge n$$ 于是,我们证明了构造方法是正确的。 ## 参考代码 ```cpp #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef long long LL; const int INF =2147483647; const int MAXN =1e3+3; int n,m,c,t,A[MAXN],f; int main(){ scanf("%d%d%d",&n,&m,&c); up(1,m,i){ scanf("%d",&t); if(t<=c/2){ up(1,n,j) if(!A[j]||A[j]>t){A[j]=t,f=j;break;} } else { dn(n,1,j) if(!A[j]||A[j]<t){A[j]=t,f=j;break;} } printf("%d\n",f); fflush(stdout); } return 0; } ```