An Easy Problem 贪心算法
2022/1/6 11:03:41
本文主要是介绍An Easy Problem 贪心算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【题目描述】
给定一个正整数N,求最小的、比N大的正整数M,使得M与N的二进制表示中有相同数目的1。
举个例子,假如给定的N为78,其二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。
【输入】
输入若干行,每行一个数nn(1≤n≤1000000),输入"0"结束。
【输出】
输出若干行对应的值。
【输入样例】
1 2 3 4 78 0
【输出样例】
2 4 5 8 83
算法解析
先进行进制转换,然后枚举求‘1’的个数,之后从n+1开始枚举查找第一个符合要求的数并输出
代码如下
#include<bits/stdc++.h> using namespace std; int n,m; string s; string q(int x)//进制转换 { string a; char ch; while(x>0) { ch=x%2+'0'; x/=2; a+=ch; } return a; } int f(string a)//计算‘1’的个数 { int k=0; for(int i=0;i<a.size();i++) if(a[i]=='1') k++; return k; } int main() { while(cin>>n) { if(n==0) return 0; s=q(n); m=f(s); for(int i=n+1;;i++) { string a=q(i); if(m==f(a)) { cout<<i<<endl; break; } } } return 0; }
这篇关于An Easy Problem 贪心算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南