p1028 [noip2001 普及组] 数的计算
时间: 2023-04-24 18:05:46 浏览: 66
题目描述
给定一个正整数 n,求有多少个 k 满足 k^2 ≤ n。
输入格式
一个整数 n。
输出格式
一个整数,表示满足条件的 k 的个数。
输入样例
10
输出样例
3
算法1
(暴力枚举) $O(\sqrt{n})$
枚举从 1 到 $\sqrt{n}$ 的整数,统计满足条件的个数。
时间复杂度
参考文献
python3 代码
C++ 代码
算法2
(二分查找) $O(\log n)$
二分查找满足 k^2 ≤ n 的最大的 k 值,然后返回 k。
时间复杂度
参考文献
C++ 代码
相关问题
P1043 [NOIP2003 普及组] 数字游戏
题目描述
有一个长度为n(n<=100)的数字串,求出其中所有的连续子串中,各个数位数字之和的最大值是多少。
输入格式
第一行是一个整数n(n<=100)。
第二行是n个数字字符。
输出格式
一个整数,表示各个数位数字之和的最大值。
样例输入
6
123123
样例输出
9
提示
此题也可用O(n)的时间复杂度求解。
算法1
(暴力枚举) $O(n^3)$
枚举出所有的连续子串,再计算它们的各位数字之和。
时间复杂度
枚举子串需要 $O(n^2)$ 的时间,每次计算各位数字之和,需要 $O(n)$ 的时间,所以总时间复杂度为 $O(n^3)$。
空间复杂度
不需要额外的空间,所以空间复杂度为 $O(1)$。
算法2
(动态规划) $O(n)$
设置一个数组 $f[i]$ 表示以第 $i$ 个位置结尾的子串中各位数字之和的最大值,那么 $f[i]$ 的值可以从两个位置转移而来:
- $f[i] = max(f[i], f[i-1] + num[i])$,即当前位置的值加上前一个位置的最大值;
- $f[i] = max(f[i], num[i])$,即当前位置的值比前一个位置的最大值更大。
转移方程为:$f[i] = max(f[i], f[i-1]+num[i], num[i])$。
时间复杂度
只需要遍历一次数组,所以时间复杂度为 $O(n)$。
空间复杂度
需要一个 $f$ 数组来记录各个位置的最大值,所以空间复杂度为 $O(n)$。
C++ 代码
算法1
p2669 [noip2015 普及组] 金币
题目描述
有 n 个金矿,第 i 个金矿可开采出金子的数量为 g[i],需要的工人数为 p[i]。有 m 个工人,每个工人只能开采一个金矿,每个金矿最多只能开采一次。
现在需要你编写一个程序,计算出在不超过 m 个工人的情况下,最多可以获得多少金子。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示每个金矿可开采出的金子数量 g[i]。
第三行包含 n 个整数,表示每个金矿需要的工人数 p[i]。
输出格式
输出一个整数,表示在不超过 m 个工人的情况下,最多可以获得多少金子。
输入样例
5 10
400 500 200 300 350
5 5 3 4 3
输出样例
900
数据范围
1≤n≤1000,1≤m≤10000,0≤g[i],p[i]≤1000
解题思路:
采用动态规划的方式解决。定义状态f(i,j)表示对前i个金矿,用j个工人最多可获得的金子数。
则转移方程为f(i,j)=max{f(i-1,j),f(i-1,j-p[i])+g[i]}
其中f(i-1,j)表示不选择第i个金矿,f(i-1,j-p[i])+g[i]表示选择第i个金矿。
边界条件为f(i,0)=0,f(0,j)=0。
最终答案为f(n,m)。
时间复杂度分析:
共有n*m个状态,每个状态都需要进行一次状态转移,则总时间复杂度为O(nm)。
参考代码:
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)