当前位置:网站首页>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;
}
边栏推荐
- Gartner authority predicts eight development trends of network security in the next four years
- Pointer elementary of C language
- URL 返回nil 以及urlhash处理
- Bit band operation of semaphore protection
- Hidden iframe design details of SAP ui5 fileuploader
- Flex弹性盒布局2
- Smart fish tank design based on stm32
- 三表联查3
- 移动端基础
- Understand the staticarea initialization logic of SAP ui5 application through the initialization of fileuploader
猜你喜欢

立创EDA——原理图的布局与检查(三)

合工大苍穹战队视觉组培训Day7——视觉,jetson naon与D435i

Flex弹性盒布局

Two table joint query 1

Shell programming specifications and variables

立创EDA——PCB的布局(四)

Hidden iframe design details of SAP ui5 fileuploader

通过 FileUploader 的初始化,了解 SAP UI5 应用的 StaticArea 初始化逻辑

Technical practice dry goods | from workflow to workflow

Built in object (bottom)
随机推荐
Three table joint query 1
[SAML SSO solution] Shanghai daoning brings you SAML for asp NET/SAML for ASP. Net core download, trial, tutorial
腾讯云上传使用
Gradient ring progress bar
Advanced pointer of C language
项目练习:表格的查改功能
Node package depends on download management
What is JSP?
Microsoft silently donated $10000 to curl, which was not notified until half a year later
合工大苍穹战队视觉组培训Day8——视觉,目标识别
信号量保护之位带操作
Neural network implementation of handwritten numeral classification matlab
Mobile page layout
Enumeration and union of C language
js中的函数
Design details of hidden iframe and form elements used by SAP ui5 fileuploader
How does vs2019 C language run multiple projects at the same time, how to add multiple source files containing main functions in a project and debug and run them respectively
移动端页面布局
Following the example of IE, is the decline of Firefox inevitable?
基于STM32的智能鱼缸设计