UVA 10125 - Sumsets

제목: n 개의 수 를 제시 하고 n 개의 수 에서 a + b + c = d 를 만족 시 키 는 조합 을 찾 아 출력 d, 출력 'no soluution' 이 존재 하지 않 습 니 다. (주의 d 요구 최대)
문제 풀이 방향: 먼저 n 개의 수 를 정렬 합 니 다. d 는 가장 큰 숫자 부터 옮 겨 다 니 고 a 도 가장 큰 숫자 부터 옮 겨 다 닙 니 다. b 는 마침 a 보다 작은 숫자 부터 옮 겨 다 닙 니 다. c 는 가장 작은 숫자 에서 옮 겨 다 닙 니 다. b < c 까지 a + b + c > d 라면 b 는 작은 수치 로 이동 해 야 합 니 다. 반대로 c 는 큰 수치 로 이동 해 야 합 니 다. 같은 때 는 만족 하 는 상황 입 니 다.
#include <cstdio>
#include <algorithm>
using namespace std;
int a, b, c, d, n, arr[1005];

bool judge() {
	for (d = n - 1; d >= 0; d--)
		for (a = n - 1; a > 0; a--)
			for (b = a - 1, c = 0; b > c && a != d; )
				if (arr[a] + arr[b]+ arr[c] == arr[d])
					return true;
				else 
					arr[a] + arr[b] + arr[c] < arr[d] ? c++ : b--;

	return false;
}

int main() {
	while (scanf("%d", &n), n) {
		for (int i = 0; i < n; i++)
			scanf("%d", &arr[i]);
		sort(arr, arr + n);
		judge() ? printf("%d
",arr[d]) : printf("no solution
"); } return 0; }

좋은 웹페이지 즐겨찾기