글 읽기 - 8986번.. 솔루션을 아는데..ㅠㅠ

skan1543 8년 전 0

솔루션이

{ x[1]이 1개, x[2]/2가 2개, x[3]/3이 3개... x[n-1]/(n-1)가 n-1개} 있는 원소들의 집합에서

중간값을 찾고.. 중간값을 x[n]-x[n-1], 즉 전봇대끼리의 간격으로 설정하는것이 최적의 해를 구하는것이다. 로 알고있습니다.

근데.. 별로 복잡한 알고리즘도 아니라 구현도 쉽게 했는데, 틀렸습니다가 뜨네요 ㅠㅠ

나름 데이터도 만들어보구해도.. 모르겠어요!!

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

struct oh {
	double xx;
	int idx;
}; oh ohh[100001]={0,};

int x[100001]={0,};
double xx[100001]={0.0,};

int cmp(const void *a, const void *b)
{
     struct oh *tempA = (struct oh *)a;//(1)
     struct oh *tempB = (struct oh *)b;//(2)
	 return tempA->xx>tempB->xx;
}

int main()
{
	int k;

	scanf("%d",&k);

	int i;

	ohh[0].xx=0;
	for(i=0;i<k;i++) 
	{
		scanf("%d",&x[i]);
		if(i!=0) x[i]-=x[0];
		
		if(i!=0){
			ohh[i].xx=x[i]/(double)i;
			ohh[i].idx=i;
		}
	}
	qsort(ohh,k,sizeof(oh),cmp);

	int mid=(k-1)*k/2;
	mid+=1; mid/=2;

	for(i=1;i<k;i++)
	{
		mid-=ohh[i].idx;
		if(mid<=0)
		{
			int temp=ohh[i].xx;
			temp*=10; temp+=5;
			temp/=10;
			int cnt=0;
			for(i=1;i<k;i++)
			{
				cnt+=abs(x[i]-temp*i);
			}
			printf("%d\n",cnt);
			break;
		}

	}

}

hahaha 8년 전 0

일단 문제에 나와있는 힌트를 참고해보세요 :)

힌트

중간 계산 결과와 출력할 값이 32비트 정수형 범위를 벗어날 수 있으니 64비트 정수형을 이용할 것을 권장한다.

skan1543 8년 전 0

아.. 제출할땐 cnt를 long long int로 바꿔서 제출해봤습니다만, 안되더라구요 ㅠㅠ

댓글 감사합니당 ^^

Nada 8년 전 0

풀이 방법 자체가 틀렸습니다.

중간값으로 생각하면 안되는 문제로 기억하고 있습니다.

0 9 10 11

정답인데 위의 소스는 12의 값을 출력하네요.

cnt가 32bit인 것도 오답의 원인 중 하나입니다.

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

문제

문제

출처

ICPC

8986번.. 솔루션을 아는데..ㅠㅠ

skan1543 8년 전 0

hahaha 8년 전 0

skan1543 8년 전 0

Nada 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말