题解 CF896B 【Ithea Plays With Chtholly】
囧仙
2020-08-12 00:35:39
## 题目大意
有 $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;
}
```