阅读原文
这是一道 \(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\) 层时停止，输出答案即可。
如有疑问，评论区见！
代码如下：
#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; }转载于:https://www.cnblogs.com/Peter0701/p/11285820.html
相关资源：JAVA上百实例源码以及开源项目