社区讨论

关于一个代码细节的疑问

P4072[SDOI2016] 征途参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m6lq2801
此快照首次捕获于
2025/02/01 12:57
去年
此快照最后确认于
2025/11/04 10:07
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
typedef long long ll;
const int N = 3e3 + 5;

int n, m, que[N], l, r;
ll a[N], f[N], g[N];
ll X(int i) { return a[i]; }
ll Y(int i) { return f[i] + a[i] * a[i]; }
double K(int i, int j) { return double(Y(i) - Y(j)) / (X(i) - X(j)); }

int check(ll mid) {
    l = r = 0;
    for (int i = 1; i <= n; ++i) {
        while (l < r && K(que[l], que[l + 1]) < a[i] * 2.0) ++l;
        f[i] = f[que[l]] + (a[i] - a[que[l]]) * (a[i] - a[que[l]]) + mid;
        g[i] = g[que[l]] + 1;
        while (l < r && K(que[r - 1], que[r]) >= K(que[r - 1], i)) --r;
        que[++r] = i; 
    } return g[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", a + i), a[i] += a[i - 1];
    ll l = 0, r = a[n] * a[n], mid;
    while (l < r)
        if (check(mid = l + r >> 1) <= m) r = mid;
        else l = mid + 1;
    check(r); printf("%lld", (f[n] - r * m) * m - a[n] * a[n]);
    return 0;
}
为什么我将第 15 行的
CPP
while (l < r && K(que[l], que[l + 1]) < a[i] * 2.0) ++l;
改成
CPP
while (l < r && K(que[l], que[l + 1]) <= a[i] * 2.0) ++l;
(把 << 改成了 \le)就 90 pts 了?

回复

1 条回复,欢迎继续交流。

正在加载回复...