CF952E 题解

这是一道 $CodeForces$ $2018$ 年愚人节比赛的 $E$ 题。 题意是给出 $n$ 块奶酪的名字（确保每块名字不同）和硬度（分为软和硬两种），请将其放入一张特制的国际象棋棋盘内，使得软硬奶酪分开（行和列上都不允许有连续的相同硬度的奶酪）。求出棋盘最小的边长（每格算作 $1$ 个单位长度）。 因为保证每块奶酪名字不同，最后排入棋盘时也与奶酪名无关，所以读入后可以直接舍弃。软硬度的大小才是关键。又因为排入棋盘时与奶酪顺序无关，所以只需要记录总的软奶酪数和硬奶酪数。 先分析 $x$ 层的棋盘可以放多少软奶酪和硬奶酪。若 $x$ 为偶数，则两种奶酪均可以放 $\frac{x \times x}{2}$ 块；若 $x$ 为奇数，则一种奶酪可以放 $\frac{x \times x}{2}$ 块，另一种奶酪可以放 $\frac{x \times x}{2}+1$ 块。 由此可得， $n \leqslant 100$ 时，棋盘边长最多为 $\lceil \sqrt{100 \times 2} \rceil =15$ ，因此我们可以枚举奶酪的边长。 边长为 $1$ 时，一定只能放下一块奶酪，故 $n=1$ 时直接特判即可。剩余的 $n$ 值直接从边长为 $2$ 开始枚举即可。枚举到 $x$ 层时，若满足了记录的软奶酪数和硬奶酪数条件，就直接输出答案即可。否则枚举到 $15$ 层时停止，输出答案即可。 如有疑问，评论区见！ 代码如下： ```cpp #include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,s,h,ans; char str[15]; inline int geta(int k) { if(k==15) return k; int tmp1=k*k/2; if(k&1) { int tmp2=k*k-tmp1; if((s<=tmp1&&h<=tmp2)||(s<=tmp2&&h<=tmp1)) { if(s+h<=k*k) return k; } return geta(k+1); } else { tmp1=k*k/2; if(s<=tmp1&&h<=tmp1) { if(s+h<=k*k) return k; } return geta(k+1); } } int main() { n=read(); if(n==1) { puts("1"); return 0; } for(register int i=1;i<=n;i++) { cin>>str; cin>>str; if(str[0]=='s'&&str[1]=='o'&&str[2]=='f'&&str[3]=='t') s++; else h++; } ans=geta(2); printf("%d\n",ans); return 0; } ```