傳送門

兩種方法做這道題。

1、二分答案。

2、因為所求的表達式是一個斜率的形式，所以維護一個凸包。然后對于每一個右端點在凸包上找一個使其最大的值就可以了。

#include<cstdio> #include<iostream> using namespace std; inline char nc() {static char b[100000],*s=b,*t=b;return s==t&&(t=(s=b)+fread(b,1,100000,stdin),s==t)?-1:*s++; } template < class T > inline void read(T &x) {char b = nc(); x = 0; bool f = 0;for (; !isdigit(b); b = nc()) if (b == '-') f = 1;for (; isdigit(b); b = nc()) x = x * 10 + b - '0'; if (f) x = -x; } typedef long long ll; typedef double db; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} const int N = 1000010; int n, k, z[N], top, x, y; ll s[N], P, Q, G; db tans; bool judge(int a, int b, int c) {return (s[b] - s[a]) * (c - b) > (s[c] - s[b]) * (b - a); } db calc(int a, int b) {return db(s[b] - s[a]) / (b - a); } void upd(int p) {int l = 1, r = top, ll, rr;while (r - l > 3) {ll = (r - l + 1) / 3 + l;rr = (r - l + 1) / 3 * 2 + l;calc(z[ll], p) < calc(z[rr], p) ? l = ll : r = rr;}for (ll = l++; l <= r; ++l)if(calc(z[l], p) > calc(z[ll], p)) ll = l;db res = db(s[p] - s[z[ll]]) / (p - z[ll]);if (res > tans) tans = res, x = z[ll], y = p; } int main() {read(n); read(k); tans = -1e9;for (int i = 1; i <= n; ++i) read(s[i]), s[i] += s[i-1];for (int i = 0; i <= n - k; ++i) {while (top > 1 && judge(z[top-1], z[top], i)) --top;z[++top] = i; upd(i + k);} P = s[y] - s[x]; Q = y - x; G = gcd(P, Q);if (G < 0) G = -G; P /= G; Q /= G;printf("%lld/%lld\n", P, Q);return 0; } /* int n, k, pb[N]; ll a[N], sa[N], P, Q, G; db b[N]; bool check(db m) {for (int i = 1; i <= n; ++i) {b[i] = b[i-1] + a[i] - m;pb[i] = (b[i] < b[pb[i-1]]) ? i : pb[i-1];}for (int i = k; i <= n; ++i) {if (b[i] - b[pb[i-k]] > 0)return P = sa[i] - sa[pb[i-k]], Q = i - pb[i-k], true;} return false; } int main() {read(n); read(k);for (int i = 1; i <= n; ++i) read(a[i]);for (int i = 1; i <= n; ++i) sa[i] = sa[i-1] + a[i];db l = -1e8, r = 1e8;for (int i = 0; i < 100; ++i) {db m = (l + r) / 2;check(m) ? l = m : r = m;} G = gcd(P, Q); if (G < 0) G = -G;if (G) P /= G, Q /= G;printf("%lld/%lld\n", P, Q);return 0; } */

?

轉載于:https://www.cnblogs.com/p0ny/p/8018378.html

總結

以上是生活随笔為你收集整理的bzoj 5090 组题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。