CodeForces - 830C Bamboo Partition(数学+推公式)

题目链接：点击查看

题目大意：给出 $n$ 个位置可以种竹子，每个位置的竹子的高度需要到达 $a_i$，所有竹子每天都会长高一个单位高度，同样每个竹子可以在任意位置砍一次，砍过之后竹子将不再长高，现在需要每隔 $d$ 天来砍一次竹子，问在保证砍下来的总高度小于等于 $k$ 的前提下，$d$ 的最大值是多少

题目分析：首先不难看出，在 $d$ 确定的前提下，所有竹子都应该长到 $d$ 的一个整数倍，写成公式的形式如下：
$$\begin{array}{rl}& \sum _{i=1}^n(d\ast \lceil \frac{a_i}{d}\rceil -a_i)\le k\\ & \Rightarrow \sum _{i=1}^n(d\ast \lceil \frac{a_i}{d}\rceil )\le k+\sum _{i=1}^n{a}_i\\ & \Rightarrow d\ast \sum _{i=1}^n\lceil \frac{a_i}{d}\rceil \le k+\sum _{i=1}^n{a}_i\end{array}$$

不难看出公式右侧是一个常量，而公式左侧是一个关于 $d$ 作为变量的乘积式子，所以可以枚举 $d$ 作为右侧公式的因子然后去检查是否合法

代码：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int n; LL sum,a[N],ans; void cal(LL d) {LL res=0;for(int i=1;i<=n;i++) res+=(a[i]+d-1)/d*d;if(res<=sum) ans=max(ans,d); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);read(n),read(sum);for(int i=1;i<=n;i++) read(a[i]),sum+=a[i];for(LL i=1;i*i<=sum;i++) cal(i),cal(sum/i);write(ans);return 0; } 超强干货来袭 云风专访：近40年码龄，通宵达旦的技术人生

总结

以上是生活随笔为你收集整理的CodeForces - 830C Bamboo Partition(数学+推公式)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。