Задача 524

[NEME$iS]

Алгоритм вкратце: построим график функции, где по горизонтальной оси возьмем расстояние между буйками, по вертикали - суммарный сдвиг. В какой-то точке по горизонтали получится минимум этой функции, осталось только определить, в какой именно. Делим горизонталь на три части (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]);
}

524 на сгу?

[NEME$iS]

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

Так, запишем целевую функцию которую вы минимизируете:


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

Но меня дико смущает то, что вы фиксируете каждую из хреней во внешнем цикле. Так же нельзя (или у вас есть доказательство?). При фиксированном h ваша функция:

минимизируется очевидно медианой чисел , а она, как видите, во-первых, зависит от h, а во-вторых, вовсе даже необязательно совпадает с какой нибудь из хреней.

Так что откажитесь от этой дурацкой идеи фиксировать каждую хрень, и честно вычисляйте медиану во внутреннем цикле

ну чё, ac или не ac?

[NEME$iS]

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