程序解数学题.pdf
需积分: 0 29 浏览量
2023-10-04
13:12:31
上传
评论 1
收藏 220KB PDF 举报
程序解数学题
M0008 数学剪枝
问题描述
数学狂魔小明，总是疯狂学习数学。他家院子里有若干颗竹子，每颗都超过1米，经常需要修剪。
小明总是找所有最高的高度为h的竹子，一次把这些竹子都修剪为√(h+1)（向下取整）高度。小明不断重
复这个过程，问最少需要几次能将所有竹子都修剪成高度为1米？
输入：
第一行为正整数n，表示竹子的数量。
第二行有n个整数hi，n>=1且1<=hi<=10^18，表示开始时竹子的高度。
输出：
一个整数，最少的修剪次数。
样例输入
7
1 3
问题分析：
高度为1的竹子不需要修剪。
相同高度的竹子只需要考虑其中的1个。
/* M0008 数学剪枝 */
#include <iostream>
#include <set>
#include <cmath>
using namespace std;
typedef long long LL;
LL h;
set<LL> s;
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h;
if (h > 1LL) s.insert(h);
}
int cnt = 0;
while (!s.empty()) {
cnt++;
h = floor(sqrt(*s.rbegin() + 1));
s.erase(*s.rbegin());
if (h > 1LL) s.insert(h);
}
cout << cnt << endl;
资源评论
JIMMY679aa
- 粉丝: 1
- 资源: 1
