글 읽기 - 이거 라인스위핑으로는 안되나요?

joonas 8년 전 0

이거 적으면서 생각난건데.. 설마 순서가 고정인가요..

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	vector<int> a(n), b(m);
	for(int i=0; i<n; ++i) scanf("%d", &a[i]);
	for(int i=0; i<m; ++i) scanf("%d", &b[i]);
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	
	if(n > m){
		// a(n)이 항상 작은 배열
		swap(a, b);
		swap(n, m);
	}
	
	int ptr = -1, sum = 0;
	for(int i=0; i<n; ++i){
		int val = INF;
		for(int j=ptr+1; j<=m-(n-i); ++j){
			if(val > abs(a[i]-b[j])){
				val = abs(a[i]-b[j]);
				ptr = j;
			}
		}
		sum += val;
	}
	printf("%d", sum);
	
	return 0;
}

joonas 8년 전 0

반례를 찾았습니다.

3 6
10 20 30
9 10 11 100 101 102

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이거 라인스위핑으로는 안되나요?

joonas 8년 전 0

joonas 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말