applese的生日

NC15501. applese的生日

描述

最可爱的applese生日啦，他准备了许多个质量不同的蛋糕，想请一些同学来参加他的派对为他庆生，为了不让一部分同学感到不爽，他决定把每个蛋糕都分割成几份（也可以不分割），使得最小的蛋糕的质量与最大的蛋糕的质量的比值不小于一个值。但是applese的刀功并不是很好，所以他希望切尽量少的刀数使得所得到的蛋糕满足条件。由于applese为了保证每一块蛋糕的质量和期望的没有偏差，所以他一刀只能切下一块蛋糕，即将一块蛋糕分成两块，同时，他不能一刀同时切两块蛋糕，也就是说，applese一次只能将一块蛋糕分割成两块指定质量的蛋糕，这两块蛋糕的质量和应等于切割前的蛋糕的质量。Applese还急着准备各种派对用的饰品呢，于是他把这个问题交给了你，请你告诉他至少要切割几次蛋糕

输入描述

第一行包括两个数T，n，表示有n个蛋糕，最小的蛋糕的质量与最大的蛋糕的质量的比值不小于T
接下来n行，每行一个数wi，表示n个蛋糕的质量

输出描述

输出包括一行，为最小切割的刀数
数据保证切割次数不超过500

示例1

输入:

0.99 3
2000 3000 4000

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 392K, 提交时间: 2020-07-12 11:17:10

#include<bits/stdc++.h>
#define db double
using namespace std;
db T,a[1010];
int n,ans;
int main()
{
    scanf("%lf %d",&T,&n);
    for(int i=1;i<=n;i++)
    scanf("%lf",&a[i]);
    sort(a+1,a+n+1);
    if(a[1]<T*a[2]&&a[2]<T*a[1]*2)
    a[1]/=2,ans++;
    for(int i=n;i>=1;i--)
    if(T*a[i]>a[1])
    ans+=ceil(T*a[i]/a[1])-1;
    cout<<ans<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 500K, 提交时间: 2018-04-06 21:13:34

#include<bits/stdc++.h>
#define db double
using namespace std;db T,a[1010];int n,ans;int main(){scanf("%lf %d",&T,&n);for(int i=1;i<=n;i++) scanf("%lf",&a[i]);sort(a+1,a+n+1);if(a[1]<T*a[2]&&a[2]<T*a[1]*2) a[1]/=2,ans++;for(int i=n;i>=1;i--) if(T*a[i]>a[1]) ans+=ceil(T*a[i]/a[1])-1;cout<<ans<<endl;}