규방 의 네 가지 수의 합 을 기다리다.

상자 안에 n 장의 카드 가 있 는데 위의 숫자 는 각각 k1, k2,..., kn 이다.네 번 의 기회 가 있 습 니 다. 한 번 씩 뽑 아서 카드 의 숫자 를 기록 하고 카드 를 상자 에 넣 으 세 요.네 개의 숫자 가 m 와 같다 면.너 는 게임 을 이 겨 라, 그렇지 않 으 면 지 는 것 이다.직감 적 으로 이 길 가능성 이 너무 낮다.이 길 가능성 이 있 는 지 없 는 지 를 판단 하 는 절 차 를 제시 하 세 요.가능 한 한 방법의 효율 을 높이다.
분석: 이 문 제 는 이전 구 글 의 확률 적 인 문제 와 유사 합 니 다. 물론 해결 방법 도 비슷 합 니 다. 여러분 은 앞의 문 제 를 찾 아서 더 이상 군말 하지 않 아 도 됩 니 다.이 문 제 는 사실 여러분 과 문 제 를 생각 하고 해법 을 개선 하 는 방향 을 이야기 하고 싶 습 니 다.
이 문제 의 가장 직접적인 방법 은 4 중 순환 으로 옮 겨 다 니 는 것 입 니 다. n ^ 4 의 시간 복잡 도 는 비교적 무 섭 지만 좋 은 출발점 입 니 다.창피 할 필 요 는 없다. 우리 가 계속 개선 하기 만 하면 된다.a, b, c 가 k1 에서 kn 까지 의 세 개의 숫자 라 고 가정 하면 d 가 존재 하 는 지, a + b + c + d = m?d 는 k1 에서 kn 에 있 습 니 다.제목 과 같은 뜻 으로 변환 등식 은 다음 과 같다. d = m - a - b - c
만약 에 상기 식 을 만족 시 키 면 k1 에서 k2 에서 d 를 찾 아야 한다. 즉, m - a - b - c 를 찾 으 면 존재 한다.찾 지 못 하면 존재 하지 않 는 다.선형 검색, 2 분 검색 등 을 찾 습 니 다.4 중 순환 의 가장 안쪽 순환 은 선형 검색 이 라 고 볼 수 있 습 니 다. 더 빨리 찾 으 려 면 2 분 검색 을 사용 할 수 있 습 니 다. 2 분 검색 은 k1 에서 kn 까지 정렬 해 야 합 니 다. 먼저 n 개의 숫자 를 정렬 하고 시간 복잡 도 O (nlogn) 를 사용 할 수 있 습 니 다.그 다음 에 가장 안쪽 순환 을 2 분 검색 으로 바 꾸 고 시간 복잡 도 는 O (n ^ 3 logn) 입 니 다.그래서 전체적인 시간 복잡 도 는 O (n ^ 3 logn) 입 니 다.
위의 분석 을 통 해 우 리 는 깨 우 침 을 얻 을 수 있다. 기왕 d 를 제기 할 수 있다 면 c 를 하나 더 제기 할 수 있다.a + b + c + d = m 를 c + d = m - a - b 로 변환 합 니 다.이렇게 하면 우 리 는 k1 에서 kn 까지 의 두 수의 합 을 매 긴 다음 에 n ^ 2 개 와 정렬 할 수 있 습 니 다. 시간 복잡 도 는 o (n ^ 2logn) 입 니 다.그리고 n ^ 2 개 와 각각 을 pair 로 설정 하여 m - pair 가 존재 하 는 지 찾 습 니 다. 같은 2 분 에 찾 습 니 다. 시간 복잡 도 는 O (n ^ 2 logn) 입 니 다.총 시간 복잡 도 는 O (n ^ 2logn) 입 니 다.
위의 층 층 이 분석 한 결과 여러분 들 은 알고리즘 의 지속 적 인 개선 에 대해 아직도 요령 이 있다 는 것 을 발견 할 수 있 습 니까? 여러분 들 은 세 심하게 깨 달 았 습 니 다.많이 깨 달 으 면 반드시 더 큰 발전 이 있 을 것 이다.구체 적 인 코드 는 다음 과 같다.

#include<iostream>
#include <algorithm>
#include<vector>
#include <set>
using namespace std;

double digtalGame1(vector<int> num,int m)//   ：    
{
	sort(num.begin(),num.end());//   
	int i1,i2,i3,length = num.size(),count = 0;
	for(i1 = 0 ;i1 < length;++i1)
	{
		for(i2 = 0;i2 < length;++i2)
		{
			for(i3 = 0;i3 <length;++i3)
			{
				int d = m - (num[i1]+num[i2]+num[i3]);
				int start = 0,end = length-1;
				while(start <= end)//                     
				{
					int mid = start + ((end - start) >> 1);
					if(num[mid] < d)start = mid +1;
					else if(num[mid] > d)end = mid -1;
					else 
					{
						count ++;
						cout << num[i1] << " " << num[i2] << " " << num[i3] << " " << d << endl;
						break;
					}
				}
			}
		}
	}
	return (1.0*count)/(length * length * length * length);
}
double digtalGame2(vector<int> num,int m)//   ：       
{
	int i1,i2,length = num.size(),count = 0;
	multiset<int> sum;
	for(i1 = 0;i1 < length;++i1)//         
	{
		for(i2 = 0;i2 < length;++i2)
		{
			sum.insert(num[i1]+num[i2]);
		}
	}
	multiset<int>::iterator iter = sum.begin();
	for(;iter != sum.end();iter++)//        ，           ，       n^2    ，       ,         ，       
	{
		int otherSum = m - *iter;
		count += sum.count(otherSum);
	}
	return (1.0*count)/(length*length*length*length);
}
int main()
{
	int n,m,i;
	while(cin >> n >> m)
	{
		vector<int> num(n);
		for(i = 0;i < n;i++)cin >> num[i];
		cout << digtalGame1(num,m) << endl;
		cout << digtalGame2(num,m) << endl;
	}
}