链接：https://www.nowcoder.com/acm/contest/80/D
来源：牛客网
最可爱的applese生日啦，他准备了许多个质量不同的蛋糕，想请一些同学来参加他的派对为他庆生，为了不让一部分同学感到不爽，他决定把每个蛋糕都分割成几份（也可以不分割），使得最小的蛋糕的质量与最大的蛋糕的质量的比值不小于一个值。但是applese的刀功并不是很好，所以他希望切尽量少的刀数使得所得到的蛋糕满足条件。由于applese为了保证每一块蛋糕的质量和期望的没有偏差，所以他一刀只能切下一块蛋糕，即将一块蛋糕分成两块，同时，他不能一刀同时切两块蛋糕，也就是说，applese一次只能将一块蛋糕分割成两块指定质量的蛋糕，这两块蛋糕的质量和应等于切割前的蛋糕的质量。Applese还急着准备各种派对用的饰品呢，于是他把这个问题交给了你，请你告诉他至少要切割几次蛋糕
输入描述:
第一行包括两个数T，n，表示有n个蛋糕，最小的蛋糕的质量与最大的蛋糕的质量的比值不小于T
接下来n行，每行一个数wi，表示n个蛋糕的质量
输出描述:
输出包括一行，为最小切割的刀数
数据保证切割次数不超过500
示例1
输入
0.99 3 2000 3000 4000
输出
6
备注:
0.5 < T < 1
1 <= n <= 1000
1 <= wi <= 1000000
题意 ：问最小切蛋糕次数，使得所有蛋糕中最小值与最大值的比值大于等于 T
思路分析 ：
首先我们要想的一个问题，蛋糕要怎么切？
平均切吗？当然是的，我们要确保的答案是最小值与最大值的比值大于等于 T ，只有当平均切的时候，才能使每块蛋糕的质量更加集中，才会使这个比值更大。
其次就比较好写了，2种方法
第一种先对蛋糕质量排序，枚举质量最小的一块的切的次数，然后从最大的质量的蛋糕往小的判断即可。
代码示例 ：
/*
* parasol
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <time.h>
using namespace std;
#define ll long long
const int maxn = 1e6+5;
const int mod = 1e9+7;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
double T;
int n;
double pre[1005], a[1005];
int ans = 0;
int sign = 0;
void fun(int x, double mm){
if (sign) return;
if (x == 0) {sign = 1; return; }
double f = mm/pre[x];
if (f > T || fabs(f-T)<eps) { // 一刀不切的时候
sign = 1;
return;
}
for(int i = 1; i <= 500; i++){
double p = (pre[x]/(i+1));
if (mm > p) f = p/mm;
else f = mm/p;
if (f > T || fabs(f-T)<eps) {
fun(x-1, min(mm, p));
}
}
}
void fun(int num){
double p = pre[1]/(num+1);
for(int i = n; i > 1; i--){
for(int j = 0; j <= 500; j++){
double f = pre[i]/(j+1);
if (fabs(p-f) < eps) {ans += j; break;}
else if (p < f) {
double x = p/f;
if (x > T || fabs(x-T) < eps){
ans+=j;
break;
}
}
else {
double x = f/p;
if (x > T || fabs(x-T) < eps){
ans+=j;
break;
}
}
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> T >> n;
for(int i = 1; i <= n; i++){
scanf("%lf", &pre[i]);
}
sort(pre+1, pre+1+n);
for(int i = 0; i <= 500; i++){
double mm = pre[1]/(i+1);
fun(n, mm);
if (sign) {
fun(i);
ans += i;
printf("%d\n", ans);
return 0;
}
}
return 0;
}
方法二 、 用优先队列
将结点定义成
struct node
{
int x; // 先前的质量
int cnt; // 切割的次数
int now; // 当前蛋糕的质量
};
每次从队列中取出最大值，看一下符不符合题意，不符合就多切一下
转载于:https://www.cnblogs.com/ccut-ry/p/8776573.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101724.html原文链接：https://javaforall.net
