글 읽기 - 카누 좀 도와주십시요..c++ c11

hswoo8 8년 전 0

제가 아는 기술은 모두 쏟아부었지만 풀 수 가 없네요 제발 도와주세요..

해싱을 쓰기위해 맵을 썼고 cin보다 scanf가 빠르고 ++i가 i++보다 빠르고 거기다

n^2배열 2개를 만들어서 해싱을 통해 k와 근접한 수를 찾도록 하려고 함니다.

j==1이 되면 빅오 n^2에 수렴하고요

원래 vector를 썼는데 배열 100만개를 선언했고

배열 초기화구문도 있는데 그건 주석처리해서 넣을게요

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;


int sort1[1000001];
int sort2[1000001];

int main(){
int a[4][1000];
   unordered_map<int, int> m;        //맵으로 해싱을 할검니다. sort1에서 값하나를 가지
	int t;
	int k, n;
	int j = 0;
	int result = 40000000;


	scanf("%d", &t);

	while (--t >= 0){

		scanf("%d %d", &k, &n);
		for (int i = 0; i<4; ++i){
			for (int j = 0; j<n; ++j){        //배열을 받고
				scanf("%d", &a[i][j]);
			}
		}
		int count = 0;		//sort1 배열 개수
		int count1 = 0;		//sort2 배열개수

		for (int i = 0; i<n; ++i){
			for (int j = 0; j<n; ++j){
				sort1[count] = (a[0][i] + a[1][j]);        //sort1이라는 n^2 배열을 만들고
				++count;
			}
		}

		for (int i = 0; i<n; ++i){
			for (int j = 0; j<n; ++j){
				sort2[count1] = (a[2][i] + a[3][j]);        //sort2라는 n^2 배열을 만들고
				++count1;
			}
		}
		j = 5;        //중요한 j  , sort1에서 한개의 값을 가지고 sort2의 값에서 -j<l<j만큼 더해서 k값이되거나 
                      //abs(l)이 j보다 작으면 j=l로 갱신하여 해싱 범위를 줄이면서 O(n^2)으로 수렴하도록..

		for (int i = 0; i<count1; ++i){		//map에 맵핑

			m[sort2[i]] = 1;
		}

		int flag = 0;

		for (int i = 0; i<count && flag == 0; ++i){

			for (int l = -j; l <= j; ++l){				//-J ~ +J 만큼 검사

				int c1 = k - sort1[i] + l;					//r = k- sort 요소 + L
				int c2 = sort1[i];
				if ((m.count(c1))){

					if (k == c1 + c2){
						cout << k << endl;
						flag = 1;
					}
					else if (abs(l) <= j){
						j = abs(l);            //l이 j보다 같거나 작으면 j= |l|로 갱신

						int temp = result;

						result = c1 + c2;
						if (l == j){                                
							if (abs(k - result) >= abs(k - temp)){    //l==j일 때 result값이 작은걸 택하도록
								if (result>temp)
									result = temp;
							}
						}

					}

				}

			}
		}
		if (flag == 0){
			cout << result << endl;
		}
		
  
	}
  m.clear();
        /*for (int i = 0; i<count; ++i){

			sort2[i] = 0;
		}for (int i = 0; i<count1; ++i){

			sort1[i] = 0;
		} */
	return 0;
}

mendou12 8년 전 0

그냥 나이브하게

배열 4개 받아서

위에꺼두개 밑에꺼두개 전부 더한 배열 2개를 만들어서

그 배열 두개에서 가장 300에 근접한 값을 찾으면 시간내로 아슬아슬하게 해결되용!

hswoo8 8년 전 0

근접한 값을 찾는데 다시 for문 쓰셨나요?

이 전에 저희가 짠 알고리즘이 전부 더한 배열 2개를 만들어서

1개를 sorting해놓고 binary search했는데 시간초과가 됬었거든요..

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

문제

문제

출처

ICPC

카누 좀 도와주십시요..c++ c11

hswoo8 8년 전 0

mendou12 8년 전 0

hswoo8 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말