POJ 2718：Smallest Difference（dfs）
(원 제 는 영어 이 고 다음은 번역 이 있 는 것)
묘사 하 다.
많은 서로 다른 소수 자릿수 를 감안 하여, 너 는 비어 있 지 않 은 부분 집합 을 선택 하여 하나의 정수 자릿수 를 형성 하고 질 서 를 쓸 수 있다.나머지 숫자 는 일부 질서 에서 두 번 째 정 수 를 형성 하 는 데 쓸 수 있다.얻 은 정수 가 0 이 아니라면 정 수 는 숫자 0 에서 시작 되 지 않 을 것 이다.
예 를 들 어 숫자 0, 1, 2, 4, 6, 7 이 있다 면 두 개의 정수 10 과 2467 을 작성 할 수 있 습 니 다.물론 이런 쌍 정 수 를 형성 할 수 있 는 방법 은 210 년 과 764 년, 204 년 과 176 년 등 이 많다.정수 간 의 차이의 절대 치 는 지난 28 세 에 위의 규칙 으로 더 작은 차 이 를 실현 할 수 있 는 다른 한 쌍 이 없다 는 사실 이 증명 되 었 다.
(제목 은 몇 개의 숫자 (0 에서 9 까지 중복 되 지 않 음) 를 주 고 이 몇 개의 숫자 로 두 개의 수 를 구성 하여 그들의 절대 치 를 최소 화 하 는 것 이다.
예 를 들 어 0, 1, 2, 4, 6, 7 을 주면 204 와 176 의 차이 가 가장 적 고 28 이 며 276, 140 을 구성 하면 가장 작은 것 이 아니다)
입력
입력 한 첫 줄 에는 병례 가 포함 되 어 있 습 니 다.모든 사례 에 대해 한 줄 의 입력 은 최소 두 개 를 포함 하지만 10 개의 소수 자릿수 를 초과 하지 않 는 다.(소수 자리 0, 1,... 9).한 줄 에 만 나타 나 는 숫자 가 없습니다.숫자 는 추가 주문 에 나타 나 빈 칸 으로 격 리 됩 니 다.
출력
모든 테스트 용례 에 대해 한 줄 에 두 개의 정수 에 쓰 는 최소 절대 차 이 는 주어진 숫자 에서 위 에서 설명 한 규칙 과 같이 쓸 수 있다.
시간 제한: 1000 ms
메모리 제한: 65536 k
Sample Input
1
0 1 2 4 6 7 Sample Out
28
#include <iostream>
#include <algorithm>
#include <cctype>
#include <cstdio>
#define MAX_N 10
using namespace std;
int a[MAX_N], n, ans;
int ArrayNum(int l, int r)
{
int num = 0;
for(int i = l; i < r; i ++)
num = num*10 + a[i];
return num;
}
void solve()
{
ans = 1E10;
do{
int m = n / 2;
if(!a[0] && m > 1)
continue;
if(!a[m] && n - m > 1)
continue;
ans = min(ans, abs(ArrayNum(0, m) - ArrayNum(m, n)));
}while(next_permutation(a, a + n));
cout << ans << endl;
}
int main()
{
int M;
cin >> M;
getchar(); // '
'
while(M --){
char ch;
n = 0;
while((ch = getchar()) != EOF){
if('
' == ch)
break;
else if(isdigit(ch))
a[n ++] = ch - '0';
}
solve();
}
return 0;
}Dfs 폭력 추가, 최대 10! =362 8800 번 으로 충분 합 니 다.
이 문 제 는 입력 한 첫 줄 이 숫자 개수 인 줄 알 았 는데 WA 가 여러 번 나 왔 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
