題意：給定一個長度為n的01串，選一個長度至少為L的連續(xù)子串，使得子串平均值最大，如果多解，子串長度應(yīng)盡量小，如果仍多解，起點編號盡量小。

分析：用了數(shù)形結(jié)合的思想，將平均值的變化用斜率表示出來，找到斜率最大的點。

作者代碼：

#include<cstdio>using namespace std;const int maxn = 100000 + 5;int n, L;char s[maxn];int sum[maxn], p[maxn]; // average of i~j is (sum[j]-sum[i-1])/(j-i+1)// compare average of x1~x2 and x3~x4int compare_average(int x1, int x2, int x3, int x4) {return (sum[x2] - sum[x1 - 1]) * (x4 - x3 + 1) - (sum[x4] - sum[x3 - 1]) * (x2 - x1 + 1);}int main() {int T;scanf("%d", &T);while (T--) {scanf("%d%d%s", &n, &L, s + 1);sum[0] = 0;for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + s[i] - '0';int ansL = 1, ansR = L;// p[i..j) is the sequence of candidate start pointsint i = 0, j = 0;for (int t = L; t <= n; t++) { // end pointwhile (j - i > 1 && compare_average(p[j - 2], t - L, p[j - 1], t - L) >= 0) j--; // remove concave pointsp[j++] = t - L + 1; // new candidatewhile (j - i > 1 && compare_average(p[i], t, p[i + 1], t) <= 0) i++; // update tangent point//找到凸點// compare and update solutionint c = compare_average(p[i], t, ansL, ansR);if (c > 0 || c == 0 && t - p[i] < ansR - ansL) {//比較結(jié)果點長度越短優(yōu)先ansL = p[i]; ansR = t;}}printf("%d %d\n", ansL, ansR);}return 0;}

?

總結(jié)

以上是生活随笔為你收集整理的uva1451的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。