怎樣高速求取一段區間的平均值 用前綴的思想來看 很easy

可是 本題題意要求的是 大于等于一段長度的區間的平均值的最大值 并且給出的數據范圍非常大 O(n*L)的直白比較算法 用于解決此問題不合適

這樣的情況下 能夠考慮用斜率來表示平均值 然后通過對斜率的討論和比較斜率來找出最大平均值

我感覺是維護一個從當前點往前的最大斜率——去除上凸點（它和當前點的連線肯定不能是最大斜率）

code（別人的orz...）

#include <stack> #include <cstdio> #include <list> #include <cassert> #include <set> #include <iostream> #include <string> #include <vector> #include <queue> #include <functional> #include <cstring> #include <algorithm> #include <cctype> #include <string> #include <map> #include <cmath> using namespace std; #define LL long long #define ULL unsigned long long #define SZ(x) (int)x.size() #define Lowbit(x) ((x) & (-x)) #define MP(a, b) make_pair(a, b) #define MS(arr, num) memset(arr, num, sizeof(arr)) #define PB push_back #define X first #define Y second #define ROP freopen("input.txt", "r", stdin); #define MID(a, b) (a + ((b - a) >> 1)) #define LC rt << 1, l, mid #define RC rt << 1|1, mid + 1, r #define LRT rt << 1 #define RRT rt << 1|1 const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; const double eps = 1e-8; const int MAXN = 1e5 + 10; const int MOD = 1e9 + 7; const int dir[][2] = { {-1, 0}, {0, -1}, { 1, 0 }, { 0, 1 } }; int cases = 0; typedef pair<int, int> pii;int Q[MAXN], arr[MAXN]; char str[MAXN];int Check(int x1, int x2, int x3, int x4) {return (arr[x2] - arr[x1-1]) * (x4-x3+1) - (arr[x4]-arr[x3-1])*(x2-x1+1); }int main() {//ROP;int T;scanf("%d", &T);while (T--){int len, L;scanf("%d%d", &len, &L);scanf("%s", str+1);for (int i = 1; i <= len; i++) arr[i] = arr[i-1] + str[i] - '0';int head = 0, tail = 0;pii ans = MP(1, L);for (int i = L; i <= len; i++){int j = i-L;while (head+1 < tail && Check(Q[tail-2], j, Q[tail-1], j) >= 0) tail--;Q[tail++] = j+1;while (head+1 < tail && Check(Q[head], i, Q[head+1], i) <= 0) head++;int tmp = Check(Q[head], i, ans.X, ans.Y);if (tmp > 0 || (tmp == 0 && i - Q[head] < ans.Y - ans.X))ans.X = Q[head], ans.Y = i;}printf("%d %d\n", ans.X, ans.Y);}return 0; }

總結

以上是生活随笔為你收集整理的1451 - Average 高速求平均值的全部內容，希望文章能夠幫你解決所遇到的問題。

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