卧薪尝胆,厚积薄发。
JC loves Mkk
Date: Sun Oct 21 11:11:01 CST 2018 In Category: NoCategory

Description:

给一个环,求一个子串,长度为偶数且在 $[L,R]$ 之间,最大化价值的平均值。
$1\leqslant n\leqslant 10^5$

Solution:

$01$ 分数规划的模型还是都很显然的,求一个前缀和,这样就变成了求 $[i-R+1,i-L+1]$ 的前缀和最小值,这个可以用一个单调队列,要求长度为偶数那就对奇数位置和偶数位置分别开一个单调队列。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
inline int read()
{
register int res = 0,f = 1;
register char c = getchar();
while(!isdigit(c))
{
if(c == '-')f = -1;
c = getchar();
}
while(isdigit(c))
{
res = (res << 1) + (res << 3) + c - '0';
c = getchar();
}
return res * f;
}
int n,L,R;
#define MAXN 100010
int a[MAXN << 1];
long long x,y;
double b[MAXN << 1];
int q[2][MAXN << 1],head[2],tail[2];
bool calc(double k)
{
for(int i = 1;i <= 2 * n;++i)b[i] = a[i] - k;
for(int i = 2;i <= 2 * n;++i)b[i] += b[i - 1];
head[0] = head[1] = 1;tail[0] = tail[1] = 0;
double ans = -100000000000;
int len;
for(int i = 1;i <= 2 * n;++i)
{
int c = (i & 1) ^ 1;
if(q[c ^ 1][head[c ^ 1]] < i - R + 1)
{
++head[c ^ 1];
}
if(i - L + 1 >= 1)
{
int p = ((i - L + 1) & 1) ^ 1;
while(head[p] <= tail[p] && b[q[p][tail[p]] - 1] >= b[i - L + 1 - 1])--tail[p];
q[p][++tail[p]] = i - L + 1;
}
if(head[c ^ 1] <= tail[c ^ 1] && b[i] - b[q[c ^ 1][head[c ^ 1]] - 1] > ans)
{
ans = b[i] - b[q[c ^ 1][head[c ^ 1]] - 1];
len = i - q[c ^ 1][head[c ^ 1]] + 1;
}
}
if(ans >= 0)y = len;
return ans >= 0;
}
typedef long long ll;
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}
int main()
{
scanf("%d%d%d",&n,&L,&R);
for(int i = 1;i <= n;++i)a[i] = read();
for(int i = 1;i <= n;++i)a[i + n] = a[i];
double l = 0,r = 1000000000,mid;
for(int i = 1;i <= 60;++i)
{
mid = (l + r) / 2;
if(calc(mid))l = mid;
else r = mid;
}
x = y * l + 0.5;
ll g = gcd(x,y);x /= g;y /= g;
if(y == 1)cout << x << endl;
else cout << x << "/" << y << endl;
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡