好希望你咕早早出交互题啊!
题解
我们并不知道它的下一个数会是多少,而且还要写满所有纸(不然你全部写在第一张纸上),所以这就有麻烦了
幸好可爱的\footnotesize{\color{skyblue}{\text{珂朵莉}}}让我们可以替换数字(不然n\lt{m}怎么办),这样就好办多了
仔细阅读英文原题面,发现在输入格式的第一行有这么一个东西:
1\leq{n\cdot{\lceil{\frac{c}{2}}\rceil}}\leq{m}\leq{1000}
由此受到启发,我们根据数与\frac{c}{2}的大小来判断放置方法,这样就行了。
很容易想到方案(假设每次给的数为x):
当x\leq{\frac{c}{2}},则正着遍历纸,第一个找到的有大于这个数的或空位置则替换/放上
反之当x\gt{\frac{c}{2}},则反着遍历纸,第一个找到的有小于这个数的或空位置则替换/放上
可以不用记录已经放了多少纸,因为你所有数都要放一遍(即放m次)
放完就立刻结束了(然后你会发现你赢了)
代码
#include<stdio.h>
int n,m,c,x,paper[1010]; //x是每次收到的数
int main()
{
scanf("%d%d%d",&n,&m,&c);
while(m--)
{
scanf("%d",&x);
if((x<<1)<=c) //情况1,x<<1表示x*2,即x*2<=c,基本等同于x<=c/2
{
for(register int i=1;i<=n;++i) //正着遍历
{
if(paper[i]>x||!paper[i]) //找到第一个符合要求的
{
paper[i]=x; //替换/放置该数
printf("%d\n",i); //输出
break; //放完就退出遍历
}
}
}
else //反之情况2
{
for(register int i=n;i;--i)
{
if(paper[i]<x||!paper[i]) //反着遍历
{
paper[i]=x; //替换/放置该数
printf("%d\n",i); //输出
break; //放完就退出遍历
}
}
}
fflush(stdout); //记得刷新输出缓冲区
}
return 0;
}
说明
关于本篇涉及到的位运算的讲解(其实就一种)
x<<1
表示x*2
,其实x<<i =x\times{2^{i}}。