题意: 给出一个长度为n的01序列, 要你求出一段至少长度为L的连续子序列, 该子序列的数字的平均值最大, 多解尽量保证长度小, 在保证起点编号尽量小, 求出起点和终点编号。
https://www.cnblogs.com/flipped/p/5202579.html
还有本校的yyf也讲的很好:https://www.cnblogs.com/yyf0309/p/6352175.html
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<stack> using namespace std; const int M = 1e5 + 5; int sum[M], q[M]; char s[M]; int xielv(int ed, int st, int eed, int sst){ return (sum[ed] - sum[st-1])*(eed - sst + 1) - (sum[eed] - sum[sst-1])*(ed -st + 1); //return 1.0*(sum[ed] - sum[st-1])/(ed - st + 1); } #define esp 1e-6 int main(){ //freopen("c.in","r",stdin); //freopen("c.out","w",stdout); int n, L; int T; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &L); scanf("%s", s); for(int i = 1; i <= n; i++)sum[i] = sum[i-1] + s[i-1] -'0'; int h = 1, t = 0; int st = 1, ed = L; for(int i = L; i <= n; i++){ while(h < t && xielv(q[t], q[t-1], i - L, q[t]) >= 0) t--; q[++t] = i - L + 1; while(h < t && xielv(i, q[h], i, q[h+1]) <= 0) h++; if(i - q[h] + 1 >= L){ int tmp = xielv(i, q[h] , ed, st); if(tmp > 0 || (tmp == 0 && i - q[h] < ed - st)) ed = i, st = q[h]; } } printf("%d %d\n",st, ed); } }View Code
有两个注意点:
1.算斜率时要用减法,除法卡精度;
2.对于代码中踢队尾的点,我用的是i-L+1,但yyf用的是i-L,因为i-L+1不在队列里,把这个循环 移到最下面,改成+1是等价的
标签:int,ed,Average,st,1451,sst,UVA,include,sum From: https://www.cnblogs.com/EdSheeran/p/9904816.html