不知哪里错了
查看原帖
不知哪里错了
701221
char_cha_ch楼主2022/12/5 18:28

md,是小数二分

#include<cstdio>
#define N 100009

inline int read()
{
	register int ret = 0;
	register bool f = 1;
	register char ch = getchar();
	while (ch < '0' || ch > '9')
		(ch == '-') ? f = 0 : 0, ch = getchar();
	while (ch >= '0' && ch <= '9')
		ret = (ret << 1) + (ret << 3) + (ch ^ 48), ch = getchar();
	return f ? ret : -ret;
}

int n;

double k;

double dp[N];

int q[N], g[N];

#include<cstring>

using std::memset;

const double eps = 1e-10;

#define slope(j, k) ((1.0 * j - 1.0 * k) / (dp[j] - dp[k]))

inline bool check(register double x)
{
	memset(q, 0, sizeof q);
	register int l = 1, r = 1, i;
	for (i = 1;i <= n;++ i)
	{
		while (l < r && slope(q[l], q[l + 1]) - eps <= 1.0 * i)
			++ l;
		dp[i] = dp[q[l]] + (i - q[l]) / i - x, g[i] = g[q[l]] + 1;
		while (l < r && slope(q[r - 1], q[r]) - eps >= slope(q[r], i))
			-- r;
		q[++ r] = i;
	}
	return g[n] >= k;
}

int main()
{
	n = read(), k = read();
	register double l = 0, r = 1e6, mid, ans;
	while (r - l >= eps)
	{
		mid = (l + r) / 2;
		if (check(mid))
			l = mid + 1, ans = dp[n] + mid * k;
		else
			r = mid - 1;
	}
	printf("%.9lf", ans);
	
	return 0;
}
2022/12/5 18:28
加载中...