TTTTTTTTTTTTTT CF 95 B 构造4,7幸运数字 贪心 构造 string
2 seconds
256 megabytes
standard input
standard output
Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.
One day Petya came across a positive integer n. Help him to find the least super lucky number which is not less than n.
The only line contains a positive integer n (1 ≤ n ≤ 10^100000). This number doesn't have leading zeroes.
Output the least super lucky number that is more than or equal to n.
题意:给你一个数字(位数<=10^100000)求不小于他且只由4,7并且4跟7的个数相等的最小的数字
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define MM(a,b) memset(a,b,sizeof(a));
char s[100000+10],s2[100000+10]; int main()
{
string s;
while(cin>>s)
{
int l=s.size();
if(l%2!=0||s>string(l/2,'7')+string(l/2,'4'))
{cout<<string(l/2+1,'4')<<string(l/2+1,'7')<<"\n";continue;}
int n4=l/2,n7=l/2; int flag=0;
string ans;
for(int i=0;i<s.size();i++)
{
int ok=0;
if(n4>0)
{
if(flag||s[i]<'4') ok=1;
else if(s[i]=='4') for(int j=i+1;j<=l;j++)
{
if(j==l) {ok=1;break;}
char ch=j-i<=n7?'7':'4';
if(ch>s[j]) ok=1;
if(ch!=s[j]) break;
}
}
if(ok) {ans+="4";n4--;}
else {ans+="7";n7--;}
if(ans[i]>s[i]) flag=1;
}
cout<<ans<<"\n";
}
return 0;
}
分析:比赛时主要是比如4500<7744这样需要构造的数字没想出来。其实还是比较简单的,
因为要让数字足够小,所以从左往右贪心的尽可能的用4,如果当前数字<4,那么肯定就用4了,但是如果等于4呢,那就无法通过当前位判断出来了,需要假设当前位放4,那么为了>=数据4500,接下来的一个位数需要尽可能大,那么就用7,比如47,当到达第三位的时候7>0,说明当前位放4虽然跟数据的数值一样,但是是可以通过后面的数字构造出一个比数据大的,所以当前位放4,否则放7
注意string放元素是a+="w";
最新文章
- window.hostory(浏览器的历史记录)
- CSS3实现鼠标移动到图片上图片变大
- fastcoloredtextbox 中文不重叠
- vue.js插件使用(01) vue-resource
- Python线性时间排序——桶排序、基数排序与计数排序
- 使用AccessibilityService模拟点击事件失败的分析
- 解决weblogic与系统时间相差8小时的问题
- 我家用的网络IP地址给定,MAC绑定,我买了个无线路由器,请问怎么设定能让我的电脑和手机都能上网
- LDAP禁止匿名访问
- jQuery 学习小结
- Python基础(set集合)
- 分别用Excel和python进行日期格式转换成时间戳格式
- CentOS7.5实践快速部署LAMP+Tomcat成功运行阿里云或者腾讯云
- mysql服务自启【Linux】
- Java大数练习
- 使用DotfuscatorPro_4.9对软件dll库进行加密
- PostgreSQL 使用小点
- EntityFrameworkCore操作记录
- python使用(二)
- 【css】css 背景色渐变兼容写法