UVa 1451 Average——斜率优化

UVa 1451 Average——斜率优化

思路紫书上写的就很好，这里只强调一点：

注意要求的斜率是（Sj - Si-1）/（j - i + 1）,一定要注意这个i-1，假如想得到前三个数的平均值，在图上就要从0开始，求0到3的平均值，而不是1到三的平均值。

说的有点抽象，还请读者琢磨一下代码里的+1-1的问题

#include #include #include #include using namespace std;const int maxn = 100000 + 10;int n, L, s[maxn], node[maxn];char str[maxn];int cross(int x1, int x2, int x3, int x4) { return (s[x2] - s[x1]) * (x4 - x3) - (s[x4] - s[x3]) * (x2 - x1);}void solve() { s[0] = 0; for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + str[i] - '0'; } int i = 0, j = 0; int ansi = 0, ansj = L; for (int t = L; t <= n; t++) { while (j - i > 1 && cross(node[j - 2], t - L, node[j - 1], t - L) >= 0) j--; node[j++] = t - L; while (j - i > 1 && cross(node[i + 1], t, node[i], t) >= 0) i++; int temp = cross(node[i], t, ansi, ansj); if (temp > 0 || (temp == 0 && t - node[i] < ansj - ansi)) { ansj = t, ansi = node[i]; } } printf("%d %d\n", ansi + 1, ansj);}int main(){ int T; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &L); getchar(); gets(str + 1); solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。