当前位置:网站首页>Maximum number less than n
Maximum number less than n
2022-07-27 17:19:00 【Folded cookies】
Give an array nums=[5,4,8,2], Give me a n=5416, Let you nums Select some elements , Make the composition number less than n The maximum number of
Ideas : greedy + Two points search
Traverse n The number on each of you , Find the highest order of a number that does not exist in the array
This bit did not change before , This bit is changed to less than n The maximum value of this bit of , The rest are nums Maximum in
If all exist , Then modify the lowest order
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Find less than idex The last one of
int searchl(vector<int>nums,int target){
int l=0,r=nums.size()-1;
while(l<r){
int mid=l+r+1>>1;
if(nums[mid]<target)l=mid;
else r=mid-1;
}
if(nums[l]<target)return nums[l];
else return -1;
}
// Find less than or equal to idex The last
int searchle(vector<int>nums,int target){
int l=0,r=nums.size()-1;
while(l<r){
int mid=l+r+1>>1;
if(nums[mid]<=target)l=mid;
else r=mid-1;
}
if(nums[l]<=target)return nums[l];
else return -1;
}
int main(){
vector<int>nums={
1,1,1};
int n=1234;
vector<int>maxn,ans;
sort(nums.begin(),nums.end());
while(n){
maxn.push_back(n%10);
n/=10;
}
int len=maxn.size();
int h=len;
for(int i=len-1;i>=0;i--){
int idx=searchle(nums,maxn[i]);
// printf("maxi=%d,idx=%d\n",maxn[i],idx);
if(idx!=maxn[i]){
h=i;
break;
}
}
if(h>=0){
for(int i=len-1;i>=0;i--){
if(i>h)ans.push_back(maxn[i]);
else if(i==h)ans.push_back(searchl(nums,maxn[i]));
else ans.push_back(nums[nums.size()-1]);
}
}else{
for(int i=len-1;i>=1;i--){
ans.push_back(maxn[i]);
}
ans.push_back(searchl(nums,maxn[0]));
}
for(int i=0;i<ans.size();i++){
printf("%d\n",ans[i]);
}
return 0;
}
边栏推荐
猜你喜欢
随机推荐
Swift QQ authorized login pit set
About paths mapping in SAP ui5 application ui5.yaml
Hegong sky team vision training Day8 - vision, target recognition
ES6 array method and pseudo array to array method
[SAML SSO solution] Shanghai daoning brings you SAML for asp NET/SAML for ASP. Net core download, trial, tutorial
20年前,他是马云最大的敌人
Global string object (function type) +math object
Passive income: return to the original and safe two ways to earn
Leader: who uses redis overdue monitoring to close orders and get out of here!
腾讯云上传使用
Hyperlink parsing in MD: parsing `this$ Set() `, ` $` should be preceded by a space or escape character`\`
KMP模板——字符串匹配
md 中超链接的解析问题:解析`this.$set()`,`$`前要加空格或转义符 `\`
三表联查1
Project exercise: the function of checking and modifying tables
Xcode 发布测试包TestFlight
Select structure
成本高、落地难、见效慢,开源安全怎么办?
在CRA创建的项目中使用@并让其识别@路径并给出路径提示
神经网络实现手写数字分类matlab








