Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 06.11.2010, 19:37
Новичок

Отправить личное сообщение для NEME$iS Посмотреть профиль Найти все сообщения от NEME$iS
 
Регистрация: 06.11.2010
Сообщений: 3

Задача 524
Алгоритм вкратце: построим график функции, где по горизонтальной оси возьмем расстояние между буйками, по вертикали - суммарный сдвиг. В какой-то точке по горизонтали получится минимум этой функции, осталось только определить, в какой именно. Делим горизонталь на три части (0-x1, x1-x2, x2-20000) и считаем значения функции в точках x1 и x2. Если функция возрастает, сдвигаем правую границу до x2, если убывает, сдвигаем левую до x1. Повторяем до тех пор, пока рассматриваемый участок не будет укладываться в погрешность eps. Повторяем циклы, фиксируя каждый из буйков, после чего выбираем из результатов лучший и выводим его.

WA на тесте 8, если кто решал, помогите разобраться плз =)

Код:
#include <stdio.h>
#include <conio.h>
#include <iostream>

using namespace std;

const double eps = 1E-8/400;
double a = 0;
double b = 20000;

double buys[20000];
double bouys[20000];
double mins[20000];
double as[20000];
double bs[20000];
int count;
double shift = 20000 * 400 + 1;

double S(double rasst, int fixed)
{
	double res = 0;
	double temp;
	bouys[fixed] = buys[fixed];
	for (int i = fixed - 1; i >= 0; i--)
	{
		bouys[i] = bouys[i + 1] - rasst;
		temp = bouys[i] - buys[i];
		if (temp < 0)
			temp = -temp;
		res += temp;
	}
	for (int i = fixed + 1; i < count; i++)
	{
		bouys[i] = bouys[i - 1] + rasst;
		temp = bouys[i] - buys[i];
		if (temp < 0)
			temp = -temp;
		res += temp;
	}
	return res;
}

void main()
{
	cin >> count;
	for (int i = 0; i < count; i++)
		cin >> buys[i];
	double x2, x3, s2, s3;
	double temp = 20000;
	for (int x = 0; x < count; x++)
	{
		while ((b - a) >= eps)
		{
			x2 = a + (b - a) / 3;
			x3 = a + (b - a) / 3 * 2;
			s2 = S(x2, x);
			s3 = S(x3, x);
			if (s2 < s3)
				b = x3;
			else if (s2 > s3)
				a = x2;
			else
			{
				a = x2;
				b = x3;
			}
		}
		mins[x] = S((b + a) / 2, x);
		as[x] = a;
		bs[x] = b;
	}
	double aMin = shift;
	int aNum = -1;
	for (int i = 0; i < count; i++)
	{
		if ((aNum == -1) || (aMin > mins[i]))
		{
			aMin = mins[i];
			aNum = i;
		}
	}
	double ssx = S((bs[aNum] + as[aNum]) / 2, aNum);
	printf("%.7f\n", ssx);
	for (int i = 0; i < count; i++)
		printf("%.7f ", bouys[i]);
}
  #2  
Старый 07.11.2010, 13:20
гость

 
Сообщений: n/a

524 на сгу?
  #3  
Старый 08.11.2010, 12:03
Новичок

Отправить личное сообщение для NEME$iS Посмотреть профиль Найти все сообщения от NEME$iS
 
Регистрация: 06.11.2010
Сообщений: 3

Да, с сгу. Это задачки с четвертьфинала чемпионата по программированию, который в октябре был, их недавно выложили =)
  #4  
Старый 08.11.2010, 12:58
гость

 
Сообщений: n/a

Так, запишем целевую функцию которую вы минимизируете:
f(h, s) = \sum_{i=1}^n |s + h \cdot i - x_i| \rightarrow \min_{h,s}

Тернарный поиск по h (расстоянию между хренями) - правильная идея, т.к. целевая функция выпукла.

Но меня дико смущает то, что вы фиксируете каждую из хреней во внешнем цикле. Так же нельзя (или у вас есть доказательство?). При фиксированном h ваша функция:
f_h(s) = \sum_{i=1}^n |(x_i - h \cdot i) - s|
минимизируется очевидно медианой чисел \{x_i - h \cdot i\}_{i=1}^n, а она, как видите, во-первых, зависит от h, а во-вторых, вовсе даже необязательно совпадает с какой нибудь из хреней.

Так что откажитесь от этой дурацкой идеи фиксировать каждую хрень, и честно вычисляйте медиану во внутреннем цикле
  #5  
Старый 09.11.2010, 17:05
гость

 
Сообщений: n/a

ну чё, ac или не ac?
  #6  
Старый 14.11.2010, 14:02
Новичок

Отправить личное сообщение для NEME$iS Посмотреть профиль Найти все сообщения от NEME$iS
 
Регистрация: 06.11.2010
Сообщений: 3

Помогло, всем огромное спа-си-бо! =))
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра