mydcwfy's Blog

P7590

Posted on
Symbols count in article: 2.1k Reading time ≈ 5 mins.

单调队列。

0. 前置知识 & 废话

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

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

本算法位置

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

1. 题意

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

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

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

2. 思路

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

1）朴素

首先考虑朴素算法。

定义

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

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

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

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

代码放置处

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

2）堆优化

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

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

不放代码了 逃。

3）单调队列

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

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

那么就可以了。

如果 $jsum[k]$，那么 j 不可能成为某个点的最小值。

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

队头是最小值。

那么就可以了 吗？ 雾。

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

3. 常数优化

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

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

4. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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;
}