cf297C

201707 （ACM）思维----构造

• 将给定的序列排序，下标从0开始。取$t=\lceil\frac{n}{3}\rceil$。
  
  • $i=0...t-1$时，$a[i]=i$
  • $i=t...n-t-1$时，$b[i]=i$
  • $i=n-t...n-1$时，$b[i]=n-1-i$
• 为什么这样构造呢？
  
  • 对于$a$数组，$a[t...n-t-1]$是可以被删除的。
  • 对于$b$数组，$b[0...t-1]$是可以被删除的。
  • 具体的分类讨论一下就行了。
    
    • $n\%3==0$，则$t=\frac{n}{3}$
    • $n\%3==1$，则$t=\frac{n+2}{3}$
    • $n\%3==2$，则$t=\frac{n+1}{3}$
• 总结
  
  • 比赛时感觉[允许$\lceil\frac{n}{3}\rceil$个重复的]这个条件无从下手。答案把$n$分成前$t$个后$t$个和中间的不足$t$个去构造。
  • 如果想到这一点的话，可能就很好想了。