BZOJ3316 JC loves Mkk

题面

样例输入

第1行,包含三个整数。$n$,$L$,$R$。
第2行n个数,代表$a[1..n]$。

样例输出

仅$1$行,表示询问答案。
如果答案是整数,就输出整数;否则,输出既约分数“$P/Q$”来表示。

思路

这题恶心啊,不过很显然可以知道这题是二分。可以直接二分最后的答案,但是$check$的复杂度貌似直接爆炸,看看这个$[L,R]$貌似可以优化的样子。考虑建立两个单调序列,对于每一个二分出的答案,在原权值上减去这个数值再做一个前缀和。那么我们的判断方法就是只要环上有任意一个长度在$[L,R]$区间中的子串的$sum[r]-sum[l]>=0$,$check$就可以$return 1$。因为长度必须为偶数,所以开始先判断一下,如果$l,r$为奇数那么就变成偶数。然后对于$L$到$2*n$(断环为链)的所有点$for$一遍每次加入$i-L$这个点的$sum$,维护一个单调上升的单调队列。然后从队头$pop$掉距离超过$R$的点。因为长度有奇偶性,所以搞两个队列维护(对于$i$为偶数长度的点对于$i+1$是奇数,但对于$i+2$又是偶数)需要注意的是记得保存最后选取的那段,然后处理输出答案。(记得开$long double$)

代码

#include<bits/stdc++.h>
#define LL long long
#define eps 1e-6
#define LB long double
#define Maxn 100005
using namespace std;
LL n,a[Maxn<<1],l,r,a1,a2,summ[Maxn<<1];
LB sum[Maxn<<1],ans;
inline void read(LL &x)
{
    LL f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
inline LL gcd(LL a,LL b)
{
	if (b==0) return a;return gcd(b,a%b);
}
inline bool check(LB x)
{
    deque<int> q[2];
    for (int i=1;i<=n<<1;i++) sum[i]=sum[i-1]+a[i]-x;
    for(int i=l;i<=n<<1;i++)
    {
        while(!q[i&1].empty()&&sum[i-l]<sum[q[i&1].back()]) q[i&1].pop_back();
        while(!q[i&1].empty()&&i-q[i&1].front()>r) q[i&1].pop_front();
        q[i&1].push_back(i-l);
        if(!q[i&1].empty()&&sum[i]-sum[q[i&1].front()]>=0) {a1=summ[i]-summ[q[i&1].front()],a2=i-q[i&1].front();return 1;}
	}
    return 0;
}
int main()
{
    read(n),read(l),read(r);
    for (int i=1;i<=n;i++) read(a[i]);
    for (int i=n+1;i<=n<<1;i++) a[i]=a[i-n];
    for (int i=1;i<=n<<1;i++) summ[i]=summ[i-1]+a[i];
  
    if (l&1) l++;if (r&1) r--; 
    LB L=0,R=1000000000;
    while (L+eps<R)
    {
        LB mid=(LB)(L+R)/2;
        if (check(mid)) ans=mid,L=mid;
        else R=mid;
    }  
    LL GCD=gcd(a1,a2);
    if (GCD==a2) cout<<a1/GCD<<endl; 
    else cout<<a1/GCD<<"/"<<a2/GCD<<endl;
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇