제8 장 욕심 + 재 귀 + 분 치 총화

비록 모두 알고리즘 의 기초 이지 만 한 후에 도 발전 한 것 을 느 꼈 다. 전기 기 초 를 잘 닦 지 않 으 면 나중에 어렵 게 배 웠 는데 이제 야 이 이 치 를 알 게 되 었 다.
잡담 은 그만 하고 VOJ 의 주제 훈련 에 참가 하 세 요. http://acm.hust.edu.cn/vjudge/contest/view.action?cid=40741#overview
1. A UVA 10602   Editor Nottoobad
러시아 NOI 의 제목 인 것 같 습 니 다. 문 제 는 n 개의 문자열 을 정 한 다음 에 문자열 의 순 서 를 재 설정 하여 마지막 에 쳐 야 할 알파벳 의 총 수 를 최소 화 하 는 것 입 니 다.현재 단 어 는 앞의 단어 와 같은 앞부분 은 때 리 지 않 고 뒤의 부분 만 때 릴 수 있 으 며 첫 번 째 단 어 는 모두 때 려 야 합 니 다.
사고방식 은 모든 입력 을 두 부분 으로 나 누 는 것 이다. 즉, 첫 번 째 단어 와 같은 자모 와 다른 나머지 단 어 를 가 진 것 이다.나머지 단 어 를 정렬 한 후 손 으로 쳐 야 할 알파벳 을 순서대로 집계 한다.같은 자 모 를 가 진 단 어 는 첫 번 째 단어 앞부분 에 몇 개의 자모 가 같은 지 통계 한 다음 에 같은 자모의 개수 에 따라 많 고 적 게 정렬 해 야 한다.마지막 으로 같은 알파벳 개 수 를 가 진 단어 에서 사전 순서에 따라 정렬 한다.이렇게 얻 은 것 은 최종 최 우선 서열 이다.
 
2. B UVA 10716   Evil Straw Warts Live
왼쪽 과 오른쪽 을 통 해 알파벳 을 바 꿀 수 있 는 문자열 을 지정 하고 최소한 의 동작 수 를 출력 할 수 있 습 니 다.
사고방식: 회 문 열 조건 을 구성 할 수 있 는 지 여 부 는 매우 간단 하 다. 홀수 길이 의 문자열 에 대해 한 글자 만 나타 나 는 횟수 가 홀수 이다.짝수 길이 의 문자열 에 대해 서 는 모든 알파벳 의 출현 횟수 가 짝수 여야 합 니 다.
관건 적 인 부분 은 가장 좋 은 교환 전략 이다. 먼저 좌우 양쪽 에서 대응 하 는 위치 문 자 를 똑 같이 하고 매번 한 쌍 을 선택 하여 양쪽 으로 이동 할 때 변화 해 야 할 위치 총 걸음 수가 가장 적은 문 자 를 선택한다.
이런 방법 은 문자열 의 길이 가 비교적 작은 경우 에 만 적용 된다. POJ 위의 문 제 는 길이 가 8000 으로 변 한 후에 이렇게 하면 시간 을 초과 할 수 있다 는 것 을 알 게 되 었 다. 그러나 당분간 더 좋 은 방법 을 생각 하지 못 했다. 혹시 dp???먼저 여기에 구 덩이 를 하나 남 겨 두 고 다음 dp 주 제 를 기다 린 후에 해결 할 수 있 습 니까?
 
3. C UVA 11100   The Trip, 2007
직접 해법 이 나 왔 습 니 다. 먼저 작은 것 부터 큰 것 까지 정렬 한 다음 에 가장 많은 수의 수 를 구하 고 d 로 기록 합 니 다. 마지막 으로 처음부터 d 를 간격 으로 배열 을 옮 겨 다 니 며 배열 이 모두 옮 겨 다 닐 때 까지 합 니 다.
 
4. D UVA 10245   The Closest Pair Problem
n 개의 점 의 좌 표를 정 하고 가장 가 까 운 두 점 사이 의 거 리 를 구하 세 요.
사고방식: 전형 적 인 분할 알고리즘 은 먼저 두 부분 으로 나 뉘 어 두 부분 에서 가장 가 까 운 점 대 거 리 를 구 해 d1, d2, d = min (d1, d2) 으로 기록 한 다음 에 두 부분 이 각각 한 점 이 있 을 때 가장 가 까 운 점 대 상황 이다.
여기 서 비둘기 새장 원리 같은 것 을 사용 해 야 하 는 것 은 매번 좌우 두 부분 에서 중간 점 이 d 범 위 를 초과 하지 않 는 그 점 을 취하 면 된다 는 것 이다.
 
5.  E UVA 11129   An antiarithmetic permutation
0, 1, 2, 3, 4... n - 1 의 서열 에 하나의 배열 을 출력 하여 그 중에서 세 가 지 를 취하 더 라 도 등차 수열 을 구성 하지 않 는 다 는 뜻 이다.
사고: 분 치 알고리즘 은 먼저 전체 서열 을 두 부분 으로 나 누 었 습 니 다. 왼쪽 부분 은 짝수 로 표 시 된 부분 입 니 다. 0, 2, 4, 오른쪽 부분 은 홀수 로 표 시 된 부분 입 니 다. 1, 3, 5.....................................
그러면 그것 은 등차 수열 을 구성 할 수 없다.다음은 왼쪽 부분 이나 오른쪽 부분 에 완전히 위치 하여 이런 수열 도 등차 가 되 지 않도록 처리 해 야 한다.좌우 부분 에 표 시 를 다시 한 후에 같은 방법 으로 재 귀적 으로 처리 하 다.
중간 에 결론 이 하나 있 는데 그것 이 바로 하나의 차이 d (d = 1, 2, 3, 4...) 의 연속 적 인 등차 수열 이다. 예 를 들 어 본 문 제 는 처음에 0, 1, 2, 3,... n - 1 로 순서대로 아래 표 지 를 정 하고 홀수 아래 표 와 짝수 아래 표 지 는 두 부분 으로 나 뉘 는데 같은 부분 에 있 지 않 은 세 개의 수 에 대해 a, b, c 는 등차 를 구성 할 수 없다.같은 부분 에서 두 수의 차 이 는 짝수 d 이 고, 다른 부분 에 있 는 것 은 홀수 d 이기 때문이다.
6.  F UVA 10041   Vito's Family
n 개의 수 를 정 하고 그 중에서 하나의 수 aj 를 구하 여 모든 수 를 그 와 상쇄 하 는 절대 치 의 합: ＞ | ai - aj | 최소 화 합 니 다.
정렬 후 중간 에 있 는 그 수 는 요구 하 는 수 aj 입 니 다.
 
7. G UVA 507 Jill Rides Again
WA 는 여러 번 을 했 습 니 다. 잘못된 제목 의 뜻 을 이해 한 것 인지 모 르 겠 습 니 다. 대체적으로 연속 적 인 하위 서열 을 구 해서 가장 크 지만 다른 조건 도 있 습 니 다. 어쨌든 그것 이 무슨 말 을 하 는 지 잘 모 르 겠 습 니 다.
일단 구 덩이 를...
8.  H UVA 108   Maximum Sum
문 제 는 2 차원 배열 과 가장 큰 하위 행렬 을 정 하 는 것 이다.
사고방식: 1 차원 상태의 최대 서브 시퀀스 로 전환 하면 된다.
모든 행위 서브 매트릭스 의 시작 경계 로 서브 매트릭스 의 높이 를 매 거 한 다음 에 서브 매트릭스 의 각 열의 합 을 구하 고 하나의 배열 a [1... n] 를 얻 은 다음 에 가장 큰 연속 서브 시퀀스 를 구한다.
동적 계획 으로 해석 할 수 있 습 니 다. dp [i] 는 a [i] 로 끝 나 는 하위 서열 의 최대 화 를 나타 내 고 전이 방정식 은 dp [i] = max (dp [i - 1], 0) + a [i] 입 니 다.
9.  I UVA 10827   Maximum sum on a torus
위의 문제 와 달리 이 2 차원 배열 은 링 위 에 있 는 것 으로 2 차원 배열 의 경계 가 서로 연결 되 어 하나의 행렬 을 구성 할 수 있다 는 것 을 의미한다.
2 차원 배열 을 2N * 2N 으로 확대 하면 됩 니 다. 즉, 4 개의 원래 의 2 차원 배열 로 구성 되 고 위의 방법 에 따라 서브 행렬 을 구하 고 서브 행렬 의 최대 높이 와 너 비 는 원래 의 배열 을 초과 해 서 는 안 됩 니 다.
 
10. J  UVA 757   Gone Fishing
n 개의 연못 이 있 습 니 다. Joe 는 연못 에서 출발 하여 0, 1, 2, n - 1 낚시 를 거 쳤 습 니 다. 연못 마다 fi 마리 의 물고 기 를 낚 을 수 있 습 니 다. 5min 마다 di 마 리 를 줄 이 고 0 이 될 때 까지 i - 1 에서 i 번 째 연못 까지 시간 이 걸 립 니 다. ti 개 5min 의 시간 이 필요 합 니 다.
주어진 h (시간) 조 에 게 최대 몇 마리 의 물고 기 를 낚 을 수 있 는 지 를 구하 세 요.
먼저 타임 은 0 번 연못 에서 출발 해 i 번 연못 까지 걸 리 는 시간 을 나타 낸다.
그리고 h * 12 > Time [i] 의 모든 연못 i, th = h * 12 - Time [i] 에 대해 0 에서 i 번 째 연못 간 에 임의로 이동 할 수 있 는 것 을 구 할 때 th 개 5min 을 써 서 가장 많이 낚 을 수 있 는 물고 기 를 구한다.연못 마다 하나의 결점 을 세우다

struct NODE {
    int num;
    int v;
    NODE() {}
    NODE(int v, int num):num(num), v(v) {}
    bool operator < (const NODE &rhs)const {
        int cmp = v - rhs.v;
        if(!cmp) return num > rhs.num;
        return cmp < 0;
    }
};

우선 대기 열 을 만 들 고 현재 물고 기 를 가장 많이 낚 을 수 있 는 연못 이 앞 에 있 으 며 번호 가 가장 작은 연못 이 앞 에 있다.
매번 첫 번 째 결점 을 꺼 내 낚시 의 연못 으로 th < = 0 또는 두 결점 에 물고기 가 없다 는 것 을 알 고 마지막 으로 남 은 시간 을 0 번 연못 에 머 무 는 시간 에 추가 합 니 다.
 
11.  K UVA 10148   Advertisement
n 개 구간 을 지정 하고 각 구간 은 최소 k 개 점 을 덮어 야 하 며 k 개 점 이 부족 한 구간 은 모든 점 을 덮어 서 선택 한 최소 점 수 를 구 합 니 다.
우선 모든 구간 을 정렬 해 야 합 니 다. 즉, 오른쪽 점 은 작은 것 에서 큰 것 으로 정렬 하고 각 구간 의 k 개 점 을 순서대로 덮어 오른쪽 점 을 우선 덮어 야 합 니 다.
12.  L UVALive 2322   Wooden Sticks
 
13.  M UVALive 2326   Moving Tables
문 제 는 주어진 n 개 구간 으로 전환 할 수 있 으 며, 매번 겹 치지 않 는 구간 을 선택 하여 모든 구간 이 선 택 될 때 까지 최소 몇 번 을 선택해 야 합 니까?각 구간 을 집계 해 점 마다 다른 구간 에 포 함 된 횟수 를 기록 할 수 있 으 며, 가장 많이 포 함 된 횟수 가 최종 결과 다.
 
14.  N UVALive 2088   Entropy
하프 만 나무.
먼저 모든 문자 에 대응 하여 하나의 결점 을 구축 한 다음 에 주파수 에 따라 정렬 하고 매번 두 주파수 의 가장 작은 결점 을 취하 여 새로운 결점 으로 합 친다. 주파 수 는 두 주파수 의 합 이 고 이 절 차 를 반복 하여 하나의 결점 만 남 을 때 까지 한다.
구체 적 으로 는 우선 대기 열 을 사용 할 수 있 으 며, NODE 결점 에 대해 서 는 주파수 우선 순위 에 따라 정렬 할 수 있 으 며, 주파수 가 작은 것 은 앞 에 배열 할 수 있다.

struct cmp {
    bool operator ()(NODE *a, NODE *b)  {
        return a->freq > b->freq;
    }
};

15.  O UVALive 2519   Radar Installation
x 축 위 에 n 개의 점 이 있 는데 x 축 에 반경 이 d 인 원 을 놓 아야 하 며 최소한 몇 개의 원 을 놓 아야 한다.
먼저 각 점 의 y 값 이 < = d 인지 판단 한 다음 에 각 점 에 대해 하나의 값 을 계산 합 니 다. v = x - sqrt (d * d - y * y);이 점 을 덮 을 수 있 는 원심 의 가장 오른쪽 위치 다.
그리고 이 값 v 에 따라 작은 것 부터 큰 것 까지 정렬 하고 v 가 가장 작은 곳 을 우선 배치 합 니 다.한번 스 캔 하면 됩 니 다.
 
16.
 
17.
 
18.
 
19. S UVALive 2911   Maximum
m 개 수 만족: ∑ xi  = b * sqrt (a), 그 중 1 < = i < = m, a, b 는 정수 이 고 a > 0, xi 는 - 1.0 / sqrt (a) ~ sqrt (a) 사이 에 있다.
max (∑ xi 의 p 차방) 를 구하 고 p 는 정 짝수 이다.
마지막 결과 가 가장 크 도록 모든 | xi | 의 값 을 최대한 크게 해 야 합 니 다. 그리고 일정한 상황 에서 xi 는 극단 적 인 방향 으로 값 을 추출 하고 최대한 많은 xi 가 sqrt (a) 를 얻 도록 해 야 합 니 다.
 
다음 욕심 알고리즘 이 있 습 니 다:
순서대로 x1... x2... xm 를 선택 하지만 매번 sum 에서 조건 을 만족 시 키 는 최대 치 를 선택해 야 합 니 다. 즉, 초기 sum = b * sqrt (a) 입 니 다. xi 의 값 을 선택 할 때마다 sum - sqrt (a) > = – 1.0 / sqrt (a), xi = sqrt (a);그렇지 않 으 면 xi = – 1.0 / sqlt (a);
또한 sum 의 값 을 계속 업데이트 합 니 다. 마지막 값 xm 는 sum 만 선택 할 수 있 습 니 다.그래 야 모든 xi 의 합 이 sum 이 고 마지막 결과 가 가장 크다.
xi 가 임의의 범위 p ~ q, p < 0 & q > 0 에 있 고 fabs (p) < fabs (q) 에 도 이러한 발견 이 있 을 수 있 습 니 다.
 
20. T UVALive 4062   You are around me ...
이 문 제 를 해결 하려 면 먼저 타원 과 긴 축의 협각 이 th 인 점 에서 타원 중심 까지 의 거리 r 가 만족 하 는 관 계 를 알 아야 한다. r ^ 2 = (a * b) ^ 2 / (asinth) ^ 2 + (bcosth) ^ 2). th 는 경사 각 이다.
그리고 문제 에서 타원 은 일정한 경각 이 있 기 때문에 공식: x '= x*cos@+y*sin@;y’ = y*cos@-x*sin @. 타원 을 수평 상태 로 돌려 야 한다.
공식 을 이용 하면 ans = pi * a ^ 2 * sqrt (1 - e ^ 2) 를 얻 을 수 있 습 니 다.즉, 두 점 을 중심 으로 하 는 타원 이 서로 접 할 때 타원 장 축 길이 다.
위의 공식 을 이용 하여 타원 중심의 거리 와 두 중심 연결선 과 긴 축의 협각 을 구 할 때마다 긴 반 축 a 를 계산 할 수 있다.
그 다음 에 분 치 알고리즘 을 이용 하면 됩 니 다. 중간 에 합병 할 때 똑 같이 양쪽 거리 가 d 를 초과 하지 않 는 점 만 취하 면 됩 니 다. 이것 은 뒷부분 과 최근 점 대 분 치 알고리즘 이 대체적으로 같다 는 것 을 증명 하기 쉽 습 니 다.
저도 잘 모 르 겠 어 요. 구체 적 으로 코드 만 볼 수 있 을 것 같 아 요. 그런데 제 코드 는 아직도 엉망 이에 요.