首页 > 试题广场 > 最大正整数
[编程题]最大正整数
  • 热度指数:404 时间限制: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)
#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)

热门推荐

通过挑战的用户