鏈接：點(diǎn)擊打開鏈接

題目描述?

? 最可愛的applese生日啦，他準(zhǔn)備了許多個(gè)質(zhì)量不同的蛋糕，想請(qǐng)一些同學(xué)來參加他的派對(duì)為他慶生，為了不讓一部分同學(xué)感到不爽，他決定把每個(gè)蛋糕都分割成幾份（也可以不分割），使得最小的蛋糕的質(zhì)量與最大的蛋糕的質(zhì)量的比值不小于一個(gè)值。但是applese的刀功并不是很好，所以他希望切盡量少的刀數(shù)使得所得到的蛋糕滿足條件。由于applese為了保證每一塊蛋糕的質(zhì)量和期望的沒有偏差，所以他一刀只能切下一塊蛋糕，即將一塊蛋糕分成兩塊，同時(shí)，他不能一刀同時(shí)切兩塊蛋糕，也就是說，applese一次只能將一塊蛋糕分割成兩塊指定質(zhì)量的蛋糕，這兩塊蛋糕的質(zhì)量和應(yīng)等于切割前的蛋糕的質(zhì)量。Applese還急著準(zhǔn)備各種派對(duì)用的飾品呢，于是他把這個(gè)問題交給了你，請(qǐng)你告訴他至少要切割幾次蛋糕

輸入描述:

第一行包括兩個(gè)數(shù)T，n，表示有n個(gè)蛋糕，最小的蛋糕的質(zhì)量與最大的蛋糕的質(zhì)量的比值不小于T 接下來n行，每行一個(gè)數(shù)wi，表示n個(gè)蛋糕的質(zhì)量

輸出描述:

輸出包括一行，為最小切割的刀數(shù) 數(shù)據(jù)保證切割次數(shù)不超過500示例1

輸入

0.99 3 2000 3000 4000

輸出

6

備注:

0.5 < T < 1 1 <= n <= 1000 1 <= wi <= 1000000

題解：

這題開始沒做出來，因?yàn)楦杏X情況會(huì)非常的復(fù)雜，沒有一點(diǎn)思路。但是看到了官方題解就很厲害了 首先有一個(gè)結(jié)論，每塊蛋糕分成的每一塊的大小都是相同的 基于這個(gè)結(jié)論，每次找到當(dāng)前劃分最大塊所在的大塊并將其劃分?jǐn)?shù)+1, 檢查是否滿足題目的要求考慮這個(gè)結(jié)論為什么是正確的：考慮一個(gè)蛋糕切的刀數(shù)不變，那么可以想到假如分割得到的塊是不同的，那么可能的獻(xiàn)是增加最大和最小之間的差值，那么這樣答案只會(huì)更劣，所以可以想到分成的每個(gè)塊的大小是相同的那么只要按照上面模擬就可以了，這題妥妥的送溫暖。 基于這個(gè)思想，我使用了map #include <bits/stdc++.h> #define mp(a,b) make_pair(a,b) using namespace std;struct Node{double ave,all;int div; }E[1007];multimap<double,int> mp; multimap<double,int>::iterator it,it2,i;void show(){i = mp.begin();for (;i != mp.end();i ++){cout << i->first << ',' << i->second << endl;}cout << "****************************" << endl; }int main() {ios::sync_with_stdio(false);double des;int n;cin >> des >> n;for (int i = 1;i <= n;i ++){cin >> E[i].all;E[i].div = 1;E[i].ave = E[i].all;mp.insert(mp(E[i].ave,i));}it = mp.begin();it2 = mp.end();it2--;//show();if (n == 1)cout << 0 << endl;else {int ans = 0;while (it->first/it2->first < des){int ID = it2->second;E[ID].div ++;E[ID].ave = E[ID].all/E[ID].div;mp.erase(it2);mp.insert(mp(E[ID].ave,ID));it2 = mp.end();it2--;it = mp.begin();ans ++;//show();}cout << ans << endl;} }

總結(jié)

以上是生活随笔為你收集整理的牛客网习题集 - Wannafly挑战赛13- D applese生日的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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