[알고리즘 · 이산 화] 이산 화의 간단 한 실현 과 운용

관련 이산 화
일부 수치의 절대 수치 가 너무 크 지만 데이터 의 개수 가 상대 적 으로 작 기 때문에 통 계 를 편리 하 게 하기 위해 무 게 를 줄 여야 한다. 우 리 는 이산 화 라 는 개념 을 도입 했다.이산 화 에서 모든 절대 수 치 는 하나의 이산 수 치 를 반영 한다.
예 를 들 어 n = 3 이 있 을 때 세 개의 수 {1 0 7, 1 0 8, 1 0 9} \ \ {10 ^ 7, 10 ^ 8, 10 ^ 9 \} {107, 108, 109} 이 세 개의 수의 절대 수 치 는 비교적 크 지만 n 이 비교적 작다. 만약 문제 가 절대 수치 에 대한 답 에 의미 가 없고 상대 적 인 크기 의 비교 나 통계 작용 만 한다 면 우 리 는 이 세 개의 수 를 {1, 2, 3} \ \ {1, 2, 3 \} 으로 바 꿀 수 있다. 이렇게 하면,우 리 는 직접 배열 로 표시 할 수 있다.
이산 화 된 절차 실현
모든 수 치 를 작은 것 에서 큰 것 으로 정렬 하여 각각 다른 수치의 첫 번 째 점 을 다른 배열 에 저장 합 니 다. 예 를 들 어 {1 0 7, 1 0 7, 1 0 8, 1 0 9} \ {10 ^ 7, 10 ^ 7, 10 ^ 8, 10 ^ 9 \} {107, 107, 108, 109} 을 다른 배열 에 투사 하면 {1 0 7, 1 0 8, 1 0 9} \ {10 ^ 7, 10 ^ 8, 10 ^ 9 \} {107, 108, 109} 입 니 다. 모든 절대적 인 수 치 를 찾 으 려 면 매 핑 배열 의 아래 표 시 를 찾 아야 합 니 다.서열 이 단 조 롭 게 증가 하기 때문에 2 분 에 찾 으 면 된다.
시간 복잡 도: O (n l o g n) O (nlogn) O (nlogn).

void discrete(void)
{
	sort(a+1,a+n+1);
	for (int i=1;i<=n;++i)
	     if (i == 1 || a[i]!=a[i-1]) b[++m]=a[i];
	for (int i=1;i<=n;++i)
	    rank[i]=lower_bound(b+1,b+n+1,a[i])-b;
}

영화
모스크바 에 서 는 n 개의 다른 나라 에서 온 과학자 가 참석 하 는 대형 국제 회 의 를 열 고 있다.
모든 과학 자 는 한 가지 언어 만 안다.
편 의 를 위해 서 우 리 는 세계 의 모든 언어 를 1 에서 109 사이 의 정수 번호 로 사용한다.
회의 가 끝 난 후 모든 과학자 들 은 함께 영 화 를 보 러 가서 휴식 을 취하 기로 결정 했다.
그들 이 가 는 영화관 에는 모두 m 편의 영화 가 상영 되 고 있 으 며, 각 영화 의 음성 과 자막 은 서로 다른 언어 를 사용한다.
영 화 를 보 는 과학자 에 게 영화 의 음성 을 알 아들 을 수 있다 면 그 는 매우 기뻐 할 것 이다.자막 을 읽 을 수 있다 면 그 는 비교적 기뻐 할 것 이다.만약 모두 모른다 면 그 는 기분 이 좋 지 않 을 것 이다.
현재 과학자 들 은 모두 가 같은 영 화 를 보기 로 결정 했다.
영 화 를 선택 하 는 것 을 도와 주세요. 영 화 를 즐 길 수 있 는 사람 이 가장 많 습 니 다.
조건 을 충족 시 키 는 영화 가 여러 편 있다 면, 이들 영화 중 가장 즐 거 운 사람 을 뽑 는 영화 다.
입력 형식 첫 줄 에 과학자 의 수 를 나타 내 는 정수 n 을 입력 하 십시오.
두 번 째 줄 은 n 개의 정수 a1, a2... an 을 입력 하 는데 그 중에서 ai 는 i 번 째 과학자 가 아 는 언어의 번 호 를 나타 낸다.
세 번 째 줄 에 정수 m 를 입력 하면 영화 의 수량 을 나타 낸다.
네 번 째 줄 은 m 개의 정수 b1, b2... bm 를 입력 하 는데 그 중에서 bi 는 제 i 영화 의 음성 이 사용 하 는 언어 번 호 를 나타 낸다.
다섯 번 째 줄 은 m 개의 정수 c1, c2... cm 를 입력 하 는데 그 중에서 ci 는 i 편 영화 의 자막 이 사용 하 는 언어 번 호 를 나타 낸다.
같은 영화 에 있어 서 비 ≠ ci 에 주의 하 세 요.
같은 줄 안의 숫자 를 빈 칸 으로 나누다.
출력 형식 은 최종 선택 한 영화 의 번 호 를 나타 내 는 정 수 를 출력 합 니 다.
만약 답 이 유일한 것 이 아니라면, 임의의 것 을 출력 해도 된다.
Solution:
이 문 제 는 이산 화의 특징 에 매우 부합된다. n, m ≤ 200000 n, m ≤ 200000 n, m ≤ 200000, n l o g n nlogn nlogn 의 시간 복잡 도 에 부합된다.답 은 언어 와 무관 하 다.
우 리 는 언어 이산 화 를 말 하려 면 2 * 8727 ° m + n 2 * m + n 2 * 8727 ° m + n 개 언어 를 이산 화 시 켜 야 한다. 시간 복잡 도: O (2 * 8727 ° m + n) l o g (2 * 8727 ° m + n) O (2 * m + n) log (2 * m + n) O (2 * 8727 ° m + n) log (2 * 8727 ° m + n) log (2 * 8727 ° m + n))
그리고 과학자 의 모든 언어 를 통 에 던 져 모든 영 화 를 매 거 져 판단 하면 된다.
코드 는 다음 과 같 습 니 다:

#include
using namespace std;
int n,m,cnt=0;
int a[200001];
int b[200001];
int c[200001];
int p[600001];
int t[600001];
int Rank[200001];
int tot[600001];
map <int,int> vis; 
void discrete(void)
{
	int N=n+2*m,cnt=0;
	sort(t+1,t+N+1);
	for (int i=1;i<=N;++i)
	    if (i == 1 || t[i] !=t[i-1]) p[++cnt]=t[i];
	for (int i=1;i<=n;++i) Rank[i]=lower_bound(p+1,p+cnt+1,a[i])-p;
	for (int i=1;i<=m;++i) Rank[n+i]=lower_bound(p+1,p+cnt+1,b[i])-p;
	for (int i=1;i<=m;++i) Rank[n+m+i]=lower_bound(p+1,p+cnt+1,c[i])-p;
}
int main(void)
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",a+i),t[i]=a[i];
	scanf("%d",&m);
	for (int i=1;i<=m;++i) scanf("%d",b+i),t[n+i]=b[i];
	for (int i=1;i<=m;++i) scanf("%d",c+i),t[n+m+i]=c[i];
	discrete();
	for (int i=1;i<=n;++i) tot[Rank[i]]++;
	//        
	int Max1=0,Max2=0,ans=1;
	
	for (int i=1;i<=m;++i)
	{
		if (tot[Rank[n+i]] > Max1) 
		{
			Max1=tot[Rank[n+i]];
			Max2=tot[Rank[n+m+i]];
			ans=i;
		}
		if (tot[Rank[n+i]] == Max1 && tot[Rank[n+m+i]]>Max2)
		{
			Max2=tot[Rank[n+m+1]];
			ans=i;
		}
	} 
	//             
	printf("%d
",ans);
	return 0;
}