# 某岛

… : "…アッカリ～ン . .. . " .. .
June 18, 2024

# Luogu P5308 [COCI2018-2019#4] Akvizna

wqs 二分显然，最多每轮得分是 1，lambda 上限可置为 1。

```const int N = int(1e5) + 9;
pair<DB, int> f[N];
int q[N], cz, op;
int n, k;

bool ok(DB lambda) {
cz = 0, op = 0; q[cz] = 0; REP_1(i, n) {
auto g = [&](int j){
return MP(f[j].fi + (DB)(i-j)/i - lambda, f[j].se + 1);
};
f[i] = {0, 0};
REP(j, i) checkMax(f[i], g(j));
}
return f[n].se <= k;
}

DB gao() {
DB l = 0, r = 1;
DO(133) {
DB m = (l + r) / 2;
ok(m) ? r = m : l = m;
}
ok(l);
return f[n].fi + l*k;
}

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
RD(n, k);
printf("%.9f\n", gao());
}

```

```const int N = int(1e5) + 9;
pair&lt;DB, int&gt; f[N];
int q[N], cz, op;
int n, k;

// f[j].fi - j/i
// b = y - kx
// f[i] , f[j], 1/i, j

DB det(DB x1, DB y1, DB x2, DB y2){
return x1<em>y2 - x2</em>y1;
}

int dett(int a, int b, int c) {
DB t = det(b-a, f[b].fi-f[a].fi, c-a, f[c].fi-f[a].fi);
return t &lt; 0 ? -1 : t &gt; 0;
}

bool ok(DB lambda) {
cz = 0, op = 0; q[cz] = 0; REP_1(i, n) {
auto g = [&amp;](int j){
return MP(f[j].fi + (DB)(i-j)/i - lambda, f[j].se + 1);
};
while (cz &lt; op &amp;&amp; g(q[cz]) &lt;= g(q[cz+1])) ++cz;
f[i] = g(q[cz]);
while (cz &lt; op &amp;&amp; dett(q[op-1], q[op], i) &gt; 0) --op;
q[++op] = i;
}
return f[n].se &lt;= k;
}

DB gao() {
DB l = 0, r = 1;
DO(133) {
DB m = (l + r) / 2;
ok(m) ? r = m : l = m;
}

<pre><code>ok(l);
return f[n].fi + l*k;
</code></pre>

}

int main() {

#ifndef ONLINE_JUDGE
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);
//freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);
#endif
RD(n, k);
printf(&quot;%.9f\n&quot;, gao());
}
```