제목에서 알 수 있듯이 작업은 다음과 같습니다.
주어진 숫자 N는 K가능한 최대 숫자를 얻기 위해 숫자를 제거 합니다. 숫자는 해당 위치에 남아 있어야합니다.
예 : n = 12345, k = 3, max = 45(처음 세 자리 숫자 제거하고 다른 위치로 이동해서는 안된다).
이 문제를 해결하는 방법을 아십니까?
(숙제가 아니라 알고리즘 콘테스트를 준비하고 온라인 심사 위원의 문제를 해결하고 있습니다.)
1 <= N <= 2^60, 1 <= K <= 20.
편집 : 여기 내 해결책이 있습니다. 작동 중입니다 :)
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
string n;
int k;
cin >> n >> k;
int b = n.size() - k - 1;
int c = n.size() - b;
int ind = 0;
vector<char> res;
char max = n.at(0);
for (int i=0; i<n.size() && res.size() < n.size()-k; i++) {
max = n.at(i);
ind = i;
for (int j=i; j<i+c; j++) {
if (n.at(j) > max) {
max = n.at(j);
ind = j;
}
}
b--;
c = n.size() - 1 - ind - b;
res.push_back(max);
i = ind;
}
for (int i=0; i<res.size(); i++)
cout << res.at(i);
cout << endl;
return 0;
}
무차별 대입은 제한에 대해 충분히 빨라야합니다 . n최대 19자릿수 를 갖습니다 . numDigits(n)비트가있는 모든 양의 정수를 생성합니다 . k비트가 설정된 경우 설정된 비트에 해당하는 위치에서 숫자를 제거합니다. 결과를 글로벌 최적과 비교하고 필요한 경우 업데이트하십시오.
복잡성 : O(2^log n * log n). 이것은 O(n)점근 적 으로 많이 그리고 똑같은 것처럼 보일 수 있지만 실제로는 훨씬 더 빠를 것입니다. 왜냐하면 로그 인 O(2^log n * log n)은 밑이 10 인 로그 이기 때문에 훨씬 더 작은 값 log base 10을 n제공 할 것 입니다 (1 + of 는 자릿수를 나타냅니다. / n).
한 번 log n에 n취한 조합 을 생성하고 각 조합을 생성 할 n - k때 선택한 n - k위치로 구성된 수를 구축 하여 요인을 피할 수 있습니다 (매개 변수로 전달). 이것은 기본적으로 비슷한 문제를 해결한다는 것을 의미합니다. given n, pick n - k digits in order such that the resulting number is maximum).
참고 : 무차별 대입을 포함하지 않는이 문제를 해결하는 방법이 있지만 주석에서 무차별 대입이 될 수있는 방법을 물었 기 때문에이 솔루션을 OP에도 보여주고 싶었습니다. 최적의 방법을 위해 왼쪽에서 오른쪽으로 숫자로 숫자를 만들면 어떤 일이 발생할지 조사하고 각 숫자 d에 대해 현재 선택된 숫자보다 작은 모든 숫자를 제거합니다. 언제 제거 할 수 있고 제거 할 수 없습니까?
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다