笔试时间：2023年8月24日 秋招

第一题

题目

小红有一个01字符串，她可以进行最多k次提作，每次操作交换相邻的两个字符，问可以得到的字典序最小的字符串是什么

输入描述

一行两个整数n和k，n,k表示字符串的长度和可以进行的操作次数接下来一行一个长度为n的01字符串。1<n<105; 1<k<109

输出描述

输出一个长度为n的字符串，表示字典序最小的字符串。

样例输入

5 2

01010

样例输出

00101

参考题解

双指针模拟，将第一个出现在1后面的0与最前面的1交换，若需要交换次数大于k,则后移指向1的指针，满足交换次数小

C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void swapChars(char& a, char& b) {
    char temp = a;
    a = b;
    b = temp;
}

vector<int> findNextPos(const string& input, int indexOne, int indexZero) {
    for (int i = indexOne; i < input.length(); i++) {
        if (input[i] == '1') {
            indexOne = i;
            break;
        }
    }
    for (int i = indexZero; i < input.length(); i++) {
        if (input[i] == '0') {
            indexZero = i;
            break;
        }
    }
    return {indexOne, indexZero};
}

int main() {
    int n, k;
    cin >> n >> k;
    string input;
    cin >> input;

    int indexOne = -1, indexZero = -1;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == '1') {
            indexOne = i;
            break;
        }
    }
    for (int i = input.length() - 1; i >= indexOne; i--) {
        if (input[i] == '0') {
            indexZero = i;
        }
    }

    if (indexZero == -1 || indexOne == -1) {
        cout << input << endl;
        return 0;
    }

    while (k > 0) {
        if (indexZero - indexOne <= k) {
            k -= (indexZero - indexOne);
            for (int i = indexOne; i <= indexZero; i++) {
                if (input[i] == '0') {
                    swapChars(input[i], input[indexZero]);
                    indexZero--;
                }
            }
        } else {
            while (indexZero - indexOne > k) {
                while (input[indexOne] != '1') {
                    indexOne++;
                }
            }
            indexOne++;
            for (int i = indexOne; i <= indexZero; i++) {
                if (input[i] == '0') {
                    swapChars(input[i], input[indexZero]);
                    indexZero--;
                }
            }
            k -= (indexZero - indexOne);
        }

        vector<int> nextPos = findNextPos(input, indexOne, indexZero);
        indexOne = nextPos[0];
        indexZero = nextPos[1];
    }

    cout << input << endl;
    return 0;
}

Java：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();;
        int k = sc.nextInt();
        sc.nextLine();
        char[] input= sc.nextLine().toCharArray();
        int indexOne = -1, indexZero = -1;
        for (int i = 0; i < input.length; i++) {
            if(input[i] == '1'){
                indexOne = i;
                break;
            }
        }
        for (int i = input.length - 1; i >= indexOne ; i--) {
            if(input[i] == '0'){
                indexZero = i;
            }
        }
        if(indexZero == -1 || indexOne == -1){
            print(input);
            return;
        }
        while(k > 0){
            if(indexZero - indexOne <= k) {
                k -= (indexZero - indexOne);
                swap(input, indexOne, indexZero);

            }else{
                while(indexZero - indexOne > k){
                    while(input[indexOne] != '1') indexOne++;
                }
                indexOne++;
                swap(input, indexOne, indexZero);
                k -= (indexZero - indexOne);
            }
            int[] next = nextPos(input, indexOne, indexZero);
            indexOne = next[0];
            indexZero = next[1];
        }
        print(input);
    }
    public static void print(char[] input){
        for (char c : input) {
            System.out.print(c);
        }
    }
    public static void swap(char[] input, int i, int j){
        char temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }

    public static int[] nextPos(char[] input, int indexOne, int indexZero){
        for(int i = indexOne; i < input.length; i++){
            if(input[i] == '1'){
                indexOne = i;
                break;
            }
        }
        for (int i = indexZero; i < input.length; i++) {
            if(input[i] == '0'){
                indexZero = i;
                break;
            }
        }
        return new int[]{indexOne, indexZero};
    }
}

Python：

def swap_chars(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def find_next_pos(input_str, index_one, index_zero):
    for i in range(index_one, len(input_str)):
        if input_str[i] == '1':
            index_one = i
            break
    for i in range(index_zero, len(input_str)):
        if input_str[i] == '0':
            index_ze