P7590题解

· · 题解

0. 前置知识 & 废话

说实话，出题人的办法我没太看懂，于是就想了另外一种方法。

本题解需要你掌握：单调队列

本算法位置

时间复杂度仍为 O(n)，但常数较标程略大，故需要点 玄学优化。

1. 题意

给你一个环，每一个点都可以加一定的权值 x，从一个点到下一个点都要减少一定的权值，要保证随时都要 x\geq0，可以在一个点时恰好为 0。

从每一个点开始时，权值都等于 0。

如果有一个点可以运动 1 周，输出最小编号，否则输出 "Failed!"。

2. 思路

出题人的方法我确实没看懂。

1）朴素

首先考虑朴素算法。

定义

d[x]=a[x]-b[x],sum[x]=\sum_{i=1}^{x}d[i]

所以如果从 i 可以到 i+1，需要满足：

a[i]=sum[i+1]-sum[i]\geq 0

我们可以考虑将环拆成 2 倍的链。

如果从 i 可以的话，需要满足：

\forall j\in [i,i+n-1],sum[j]\geq sum[i-1]

时间复杂度为 O(n^2)，期望得分 30 分。

代码放置处

实际打代码时，我们可以以它为对拍代码。

2）堆优化

其实，我们不难发现，对于该式，我们可以使用堆优化。

时间复杂度 O(n\log n)，期望得分 70 分。

不放代码了 逃。

3）单调队列

我们进一步挖掘性质，可以发现，我们需要的是 [i,i+n-1] 的最小值，且 i 不断变大。

这难道不是和单调队列相似吗？

那么就可以了。

如果 j<k,sum[j]>sum[k]，那么 j 不可能成为某个点的最小值。

维护一个单调队列，使其保持递增的顺序。

队头是最小值。

那么就可以了 吗？ 雾。

单调队列虽然是 O(n),但常数相对于标程更大，而最大 \sum n=2\times 10^7，很可能超时。

3. 常数优化

  1. 我开始 scanf+O2 竟然超时了，所以快读是时候了。
  2. 听说 register 可以加快，用一用也不错。

这样一阵 玄学 优化后，我们就不用 O2 最大点也可以只用 600ms 就过了。

4. 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define re register
#define ll long long
using namespace std;

const int N=1e6+10;

ll d[2*N],sum[2*N];
int hh,tt,q[2*N];
char c;

void insert(int x)
{
    while (hh<=tt&&sum[q[tt]]>=sum[x]) tt--;
    q[++tt]=x;
    return;
}

void get(int &x)
{
    while ((c=getchar())<'0'||c>'9') ;
    x=c-'0';
    while ((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';
}

int main()
{
    // freopen("randdata.in","r",stdin);
    // freopen("myans.out","w",stdout);
    re int cas,n,x;
    get(cas);
    while (cas--)
    {
        get(n);
        for (re int i=1;i<=n;++i) get(x),d[i]=x;
        for (re int i=1;i<=n;++i)
        {
            get(x);
            d[i]-=x;
        }
        for (re int i=1;i<=n;++i) d[i+n]=d[i];
        for (re int i=1;i<=2*n;++i) sum[i]=sum[i-1]+d[i];//,cout<<sum[i]<<' ';
        hh=1;tt=0;
        for (re int i=1;i<=n;++i) insert(i);
        re bool flag=0;
        for (re int i=1;i<=n;++i)
        {
            while (hh<=tt&&q[hh]<i) hh++;
            insert(i+n-1);
            // printf("%d %d\n",hh,tt);
            if (sum[i-1]<=sum[q[hh]])
            {
                printf("%d\n",i);
                flag=1;
                break;
            }

        }
        if (!flag) puts("Failed!");
    }
    return 0;
}