題目鏈接：點(diǎn)擊查看

題目大意：給出 $n$ 個(gè)位置可以種竹子，每個(gè)位置的竹子的高度需要到達(dá) $a_i$，所有竹子每天都會(huì)長(zhǎng)高一個(gè)單位高度，同樣每個(gè)竹子可以在任意位置砍一次，砍過(guò)之后竹子將不再長(zhǎng)高，現(xiàn)在需要每隔 $d$ 天來(lái)砍一次竹子，問(wèn)在保證砍下來(lái)的總高度小于等于 $k$ 的前提下，$d$ 的最大值是多少

題目分析：首先不難看出，在 $d$ 確定的前提下，所有竹子都應(yīng)該長(zhǎng)到 $d$ 的一個(gè)整數(shù)倍，寫成公式的形式如下：
$$\begin{array}{rl}& \sum _{i=1}^n(d??\frac{a_i}{d}??a_i)\le k\\ & ?\sum _{i=1}^n(d??\frac{a_i}{d}?)\le k+\sum _{i=1}^n{a}_i\\ & ?d?\sum _{i=1}^n?\frac{a_i}{d}?\le k+\sum _{i=1}^n{a}_i\end{array}$$

不難看出公式右側(cè)是一個(gè)常量，而公式左側(cè)是一個(gè)關(guān)于 $d$ 作為變量的乘積式子，所以可以枚舉 $d$ 作為右側(cè)公式的因子然后去檢查是否合法

代碼：

// #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; } 超強(qiáng)干貨來(lái)襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 830C Bamboo Partition(数学+推公式)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。