转载

[转载] $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\) 层时停止,输出答案即可。

如有疑问,评论区见!

代码如下:

#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

正文到此结束
本文目录