H-无尽大军 2019年安徽大学ACM/ICPC实验室新生赛(公开赛)

一道简单的递推题目。基于贪心的思想,要想花费少,应该尽可能采用翻倍再的方法,比如100的话先构造出50,再翻倍,99的话,构造出33,翻倍再一次。因此对n来说,找到它最小的质因子i,n/i就是构造n之前需要构造的军队。(题目数据范围也隐性提示了一下做法)。
个人习惯用dfs写这类问题。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n;
ll dfs(ll n) /**< 贪心思想 */
{
    if(n==1)
        return 0;
    ll i;
    for(i=2; i*i<=n; i++)/**< 找到n最小质因子 */
    {
        if(n%i==0)
            break;
    }
    if(i*i<=n)
        return i+dfs(n/i);/**< 花费正好是质因子的值,总共***i-1次,第一次花费2 */
    else
        return n;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    cout<<dfs(n);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 11:47
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
在喝茶的牛油很喜欢吃...:今天oc了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务