首页 > 代码库 > UVa1451 Average (数形结合,斜率优化)
UVa1451 Average (数形结合,斜率优化)
链接：http://vjudge.net/problem/UVA-1451
分析：http://wenku.baidu.com/link?url=ntSYLfzAWxjlfpOKGTac0XYWhtwiMKvn2k1fI__R6JsJVXR_7b9GNijgkX2dPYJqIT5ri7_HS0EmFJZBwxe4bIX8IMWNOcjsMBziIMgC1s3
斜率优化。ave(i,j)=（Sj-Si-1）/(j-i+1)|j-i+1>=L|i尽量小，检查点从L开始枚举，用队列保存被检查点，维护一个从检查点t开始数至少L个点的下凸曲线，循环先维护下凸曲线，由于至少要保证L个点，所以只关注出现在t-L和它前面出现的上凸点，因此被检查点集合(队列)中至少要有两个点，然后接下来维护切线，向被检查点集合中加入点t-L+1,这是至少L个点时的斜率，根据下凸折线斜率的单调性，如果在检查点t时找到了一个切点A，那么A之前的所有点都可以删除了；过这些点的切线斜率一定小于已知最优解，不会做出更大的贡献了。于是在队列集合中把当前切点之前的点全部删去。
1 #include <cstdio> 2 3 const int maxn = 100000 + 5; 4 5 char s[maxn]; 6 int n, L, sum[maxn], p[maxn]; 7 8 int compare_average(int x1, int x2, int x3, int x4) { 9 return (sum[x2]-sum[x1-1]) * (x4-x3+1) - (sum[x4]-sum[x3-1]) * (x2-x1+1);10 }11 12 int main() {13 int T;14 scanf("%d", &T);15 while (T--) {16 scanf("%d%d%s", &n, &L, s + 1);17 sum[0] = 0;18 for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + s[i] - ‘0‘;19 int i = 0, j = 0, ansL = 1, ansR = L;20 for (int t = L; t <= n; t++) {21 while (j-i > 1 && compare_average(p[j-2], t-L, p[j-1], t-L) >= 0) j--;22 p[j++] = t-L+1;23 while (j-i > 1 && compare_average(p[i], t, p[i+1], t) <= 0) i++;24 int c = compare_average(p[i], t, ansL, ansR);25 if (c > 0 || c == 0 && t - p[i] < ansR - ansL) {26 ansL = p[i]; ansR = t;27 }28 }29 printf("%d %d\n", ansL, ansR);30 }31 return 0;32 }
UVa1451 Average (数形结合,斜率优化)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。