首页 > 试题广场 >

最大正整数

[编程题]最大正整数
  • 热度指数:527 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
数组中存储了一堆小于10的非负整数,整个数组从左到右代表一个正整数(如数组[0, 1, 3, 2]代表正整数132)。现给出一个正整数K,要求经过K次数组相邻位置元素交换(必须完成K次交换),使得这个数组代表的数字最大。
例如, 
int array[] = {0, 1, 3, 2}, K = 1,则经过1次交换后,数组所能代表的最大值为1032;
int array[] = {0, 1, 3, 2}, K = 2,则经过2次交换后,数组所能代表的最大值为3012。

输入描述:
首先,输入一个正整数T,表示接收T组测试用例;
此后,输入T组测试用例,其中每组测试用例包含如下内容:
输入1:一个正整数K,表示在当前测试用例中,可以对数组进行K次相邻元素间的位置交换;
输入2:一个正整数N,表示当前用例包含数组的长度;
输入3:N个数组元素,所有元素都是小于10的非负整数;


输出描述:
输出共N行,对应于N个用例的输出:
每行输出为一个数组,数组元素之间用一个空格隔开,要求每行输出前后均无多余空格。
示例1

输入

4
2
5
4 2 1 3 5
3
5
4 2 1 3 5
4
5
4 2 1 3 5
5
5
4 2 1 3 5

输出

4 3 2 1 5
4 5 2 1 3
5 4 2 1 3
5 4 2 3 1

备注:
60%的数据 
70%的数据 
80%的数据 
90%的数据 
100%的数据 
100%的数据 ,60%的数据 ,100%的数据 
A[p]是否交换由 A[p]~A[p+K]决定,若存在 pm属于[p+1,min(p+1+K,N),对i 为[p+1,min(p+1+K,N)中的任意值.都有 A[pm]>A[p],且 A[pm]>=A[i],则将 A[pm]交换到 A[p]位置.K = K-(pm-p),p++;进入下一次循环;
循环条件: K>0(还有交换次数没消费) && p<N-1;
跳出循环后判断 K%2 是否等于 1;若是,则对A 的最后两个元素交换(没做这一步会有 20% 的 case 出错);
#include<iostream>
#include<vector>
#include<fstream>
using namespace std;
  
void swap(vector<unsigned> &A,unsigned i,unsigned j)
{
    for(unsigned k=j;k>i;k--)
    {
        unsigned tmp = A[k];
        A[k] = A[k-1];
        A[k-1] = tmp;
    }
}
void step(vector<unsigned> &A,unsigned p,unsigned &K)
{
    unsigned lower = p+1,upper = p+1+K;
    unsigned N = A.size();
    upper = min(upper,N);
    unsigned pm = p,max = A[p];
    for(unsigned i = lower;i<upper;i++)
    {
        if(max<A[i])
        {
            pm = i;
            max = A[i];
        }
    }
    swap(A,p,pm);
    K-=(pm-p);
}
int main()
{
    
    unsigned T;cin>>T;
    vector<vector<unsigned>> A;
    vector<unsigned> K(T,0),N(T,0);
    for(unsigned i=0;i<T;i++)
    {
        scanf("%d",&K[i]);
        scanf("%d",&N[i]);
        vector<unsigned> Ai;
          
        for(unsigned j=0;j<N[i];j++)
        {
            unsigned ai;
            scanf("%d",&ai);
            Ai.push_back(ai);
        }
        A.push_back(Ai);
    }
    for(unsigned i=0;i<T;i++)
    {
       
        unsigned p=0;
        while(K[i]>0&&p<N[i]-1)
        {
            step(A[i],p,K[i]);
            p++;
        }
        if(K[i]%2==1)swap(A[i],p-1,p);
 
        for(unsigned j=0;j<N[i];j++)
        {
            printf("%d ",A[i][j]);
        }
        printf("\n");
    }
}


编辑于 2020-07-27 14:13:48 回复(2)
def func(K, N, arr):
    for i in range(N):
        # find max swappable val in range[i+1, i+K]
        imax = i
        for j in range(i+1, min(N, i+K+1)):
            if arr[imax] < arr[j]:
                imax = j
        
        K -= imax - i  # update K val
        # psuedo swap
        val = arr.pop(imax)
        arr.insert(i, val)
 
        if K == 0:
            break  # stop when K == 0
    
    # K is too large that arr is already sorted after N iteration.
    # if K is even then arr keeps the same, because remaining swaps can be reduced
    # if K is odd, then swap the last two elements to keep arr max
    if K != 0 and K % 2 == 1:
        arr[-1], arr[-2] = arr[-2], arr[-1]

    return arr


T = int(input())
for i in range(T):
    K = int(input())
    N = int(input())
    arr = [int(val) for val in input().split()]
    print(' '.join([str(val) for val in func(K, N, arr)]))



发表于 2020-08-21 13:22:29 回复(0)
思路:
在当前位置向后k个之内查找最大值,若有则把最大值提到当前位置,k减去移动长度,当前位置向后移动一个位置,直达到达末尾。到达末尾后,如果剩余k为奇数,则为了把k用光,还需要交换末尾两个元素。
#include<bits/stdc++.h>
using namespace std;

void myswap(int s,int i,vector<int>& nums){
    int tmp=nums[i];
    for(int j=i;i>s;i--){
        nums[i]=nums[i-1];
    }
    nums[s]=tmp;
}

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int k,len;
        scanf("%d%d",&k,&len);
        int start=0;
        vector<int> nums(len,0);
        for(int i=0;i<len;i++)
            scanf("%d",&nums[i]);
        while(k&&start<len){
            int index=-1,m=0;
            for(int i=start;i<=start+k&&i<len;i++){
                if(nums[i]>m) {
                    index=i;
                    m=nums[i];
                }
            }
            if(index!=-1){
                myswap(start,index,nums);
                k-=(index-start);
            }
            start++;
       }
       if(k%2==1) swap(nums[len-2],nums[len-1]);
       for(int i=0;i<len;i++)
           printf("%d ",nums[i]);
        printf("\n");
    }
}


发表于 2022-08-08 18:13:59 回复(0)
import sys
def cout(num):
    print(' '.join([str(val) for val in num]))
    
n=map(int,sys.stdin.readline().split())[0]
for _ in range(n):
    k=map(int,sys.stdin.readline().split())[0]
    length=map(int,sys.stdin.readline().split())[0]
    nums=list(map(int,sys.stdin.readline().split()))
    res=[]
    if length==1:
        print(nums[0])
        continue
    if k==0:
        cout(nums)
        continue
    while k>0 and len(nums)>0:
        if len(nums)+1>k:
            cur=max(nums[:k+1])
        else:
            cur=max(nums)
        i=nums.index(cur)
        if i!=0:
            if i<len(nums)-1:
                nums=[nums[i]]+nums[:i]+nums[i+1:]
            else:
                nums=[nums[i]]+nums[:i]
            k-=i
            res.append(cur)
            nums.pop(0)
        else:
            res.append(cur)
            nums.pop(0)
    res+=nums
    if k>0 and k%2==1:
        tmp=res[-1]
        res[-1]=res[-2]
        res[-2]=tmp
    cout(res)
    

老是超时怎么搞啊

思路就是从前往后,以当前位置为起点得到长度为k+1的窗口,判断最大值是否在开头,交换后保持其余顺序不变,k-i。最后由于不能浪费k,所以k为奇数就交换最后两位,否则不管
编辑于 2021-04-04 22:17:05 回复(0)
麻麻,我出息了,我居然做出来了。
排版好麻烦,懒得调了。
思路就是从第一个位置开始检索,然后在K的范围内找到一个最大的换到现在检索的位置,然后减去相应的K,当所有位置都看过之后,K不为零,判断如果剩余为奇数就交换最后两个,否则为偶数就不管。
一开始使用的cout和cin还有int数组,但是第一次提交的时候提示超出内存了还是什么,我就换了scanf和printf和string来保存数据。
然后换了scanf之后发现读数据老是读不对,就又换成cin了。
#include<bits/stdc++.h> using namespace std;

int main(){     int T,K,N;     scanf("%d",&T);     while(T--){         scanf("%d %d",&K,&N);         string data = "";         for(int i = 0;i < N;i++){             char c;             cin >> c;             data+=c;         }         int pos = 0;         while(K){             if(pos == N)                 break;             char the_max = '0'-1;             int index = pos;             for(int i = 0;i <= K;i++){                 if(pos+i >= N)                     break;                 if(the_max < data[pos+i]){                     the_max = data[pos+i];                     index   = pos+i;                 }             }             if(index != pos)                 data = data.substr(0,pos) + data.substr(index,1) + data.substr(pos,index-pos) + data.substr(index+1,N-index);             K -= index - pos;             pos++;         }         if(K % 2 == 1){             char tmp = data[N-2];             data[N-2] = data[N-1];             data[N-1] = tmp;         }         for(int i = 0;i < N;i++)             cout << data[i] << " ";         cout << endl;     }
}



发表于 2021-03-27 17:25:19 回复(0)
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
 
using namespace std;
string minInteger(string num, int k) {
    if (k == 0)
        return num;
    for (char c = '9'; c >= '0'; --c) {
        int i = num.find(c);
        if (i >= 0) {
            if (i <= k) {
                return c + minInteger(num.substr(0, i) + num.substr(i + 1), k - i);
            }
        }
    }
    return num;
}
int main() {
 
    int T = 0;//正整数T T组测试用例
    int K = 0;//K次交换
    int N = 0;//N个数组元素
 
    cin >> T;
    while (T--) {
        cin >> K;
        cin >> N;
 
        string nums;
        for (int i = 0; i < N; ++i) {
            char c;
            cin >> c;
            nums += c;
        }
        string res = minInteger(nums, K);
        //reverse(res.begin(), res.end());
        for (int i = 0; i < res.length(); ++i) {
            cout << res[i] << " ";
        }
        cout << endl;
    }
     
 
    return 0;
}
通过80% 有没有大佬,帮忙指点一下
编辑于 2020-07-29 18:01:54 回复(0)

没java,那我发一个,虽然不一定是最优解,用递归做的,一次向左移动一个[0,k]区间的最大值,offset偏移量,每次递归的时候递进1,k是剩余的操作次数,最后如果到数组尾元素,就退出递归。

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for (int i = 0; i < t; i++) {
            int k = scanner.nextInt();
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for (int j = 0; j < n; j++) {
                arr[j] = scanner.nextInt();
            }
            function(0, k, arr);
            print(arr);
        }
    }

    private static void print(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println(arr[arr.length - 1]);
    }

    public static void function(int offset, int k, int[] arr) {
        if (offset == arr.length - 1) {
            if (k % 2 != 0) {
                int temp = arr[offset];
                arr[offset] = arr[offset - 1];
                arr[offset - 1] = temp;
            }
            return;
        }
        int max = arr[offset];
        int index = offset;
        for (int i = offset + 1; i <= offset + k && i < arr.length; i++) {
            if (max < arr[i]) {
                index = i;
                max = arr[i];
            }
        }
        for (int i = 0; i < index - offset; i++) {
            int temp = arr[index - i];
            arr[index - i] = arr[index - i - 1];
            arr[index - i - 1] = temp;
            k--;
        }
        if (k != 0) {
            offset++;
            function(offset, k, arr);
        }
    }

}

发表于 2020-07-28 01:34:08 回复(1)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int T, k ,N;
bool cmp (char a,char b){
    return  a > b;
}
string maxsort(string str){
    if(k >= N *(N-1) / 2) {
        sort(str.begin(),str.end(),cmp);
        return str;
    }
    if(k == 0) return str;
    for(char c = '9'; c >='0';c--){
        int i = str.find(c);
        if(i >=0 && i<=k){
             k = k - i;
            return c+maxsort(str.substr(0,i) + str.substr(i+1));
        }
    }
    return str;

}
int main(){
    cin >> T;
    int temp = T;
    while(temp--){
        scanf("%d%d", &k,&N);
        vector<int> num(N);
        for(int i = 0; i < N;i++) scanf("%d",&num[i]) ;
        string str;
        for(auto& x:num) str += x+'0';
        string str2 = maxsort(str);
        while(k > 0){
            swap(str2[N-1], str2[N-2]);
            k--;
        }
        for(auto& x:str2) printf("%d ", x-'0');

        puts("");
    }

    return 0;
}
崩溃了 只能过90% 有没有大神有好的做法,或者指点我一下

发表于 2020-07-15 16:23:38 回复(1)