ในปัญหานี้ เราได้รับค่าจำนวนเต็มสองค่า n และ k งานของเราคือ ค้นหาจำนวนสูงสุดที่เป็นไปได้โดยทำการแลกเปลี่ยน K มากที่สุด
คำอธิบายปัญหา: ในที่นี้ เราจำเป็นต้องคำนวณจำนวนที่สูงสุดและสร้างขึ้นหลังจากสลับตัวเลขได้ไม่เกิน k หลัก
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: n =538 k =1
ผลลัพธ์: 835
คำอธิบาย:
เราจะสลับ 8 และ 5
แนวทางการแก้ปัญหา
ในการแก้ปัญหา เราต้องสลับตัวเลขของตัวเลข k ครั้ง และตรวจดูว่าตัวเลขที่ออกมามีค่าสูงสุดหรือไม่
เราต้องหาตัวเลขสูงสุดของตัวเลขแล้วสลับองค์ประกอบที่ดัชนีแรก และอื่นๆ สำหรับดัชนี k ตัวแรกของตัวเลข
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void calcMaxNumAfterSwap(string number, int k, string& maxString, int n){
if (k == 0)
return;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (number[i] < number[j]) {
swap(number[i], number[j]);
if (number.compare(maxString) > 0)
maxString = number;
calcMaxNumAfterSwap(number, k - 1, maxString, n);
swap(number[i], number[j]);
}
}
}
}
int main(){
string str = "15263";
int k = 3;
int size = str.length();
string maxString = str;
calcMaxNumAfterSwap(str, k, maxString, size);
cout<<"The maximum number created after "<<k<<" swaps is "<<maxString;
return 0;
} ผลลัพธ์
The maximum number created after 3 swaps is 65321
