C++14(g++5.4) 解法, 执行用时: 123ms, 内存消耗: 40732K, 提交时间: 2020-02-15 23:56:50

#include <bits/stdc++.h>
using namespace std;
typedef double db;
#define mid ((l + r) >> 1)

const int N = 1e5 + 5;
const int M = 25;
const int bit = 18;
int n, b[N];
int ans, lg[N];
db lf[N][M], rg[N][M];

void solve(void);
bool check(int s, int x);

int main(void) { return solve(), 0; }

void solve(void) {
    scanf("%d", &n), ans = 1, scanf("%d", b + 1);
    for(int i = 2; i <= n; i++) {
        scanf("%d", b + i), lg[i] = lg[i - 1] + (i == (1 << (lg[i - 1] + 1)));
        lf[i][0] = b[i] * 1.0 / (b[i - 1] + 1);
        rg[i][0] = (b[i] + 1) * 1.0 / b[i - 1];
    }
    for(int i = 1; i <= bit; i++)
        for(int j = 1; j <= n - (1 << i) + 1; j++) {
            lf[j][i] = max(lf[j][i - 1], lf[j + (1 << (i - 1))][i - 1]);
            rg[j][i] = min(rg[j][i - 1], rg[j + (1 << (i - 1))][i - 1]);
        }
    for(int i = 1, l, r, e; i < n; i++) {
        l = i + 1, r = n;
        while(l <= r) check(i, mid) ? e = mid, l = mid + 1 : r = mid - 1;
        ans = max(ans, e - i + 1);
    }
    printf("%d\n", ans);
}

inline bool check(int s, int x) {
    db l = max(lf[s + 1][lg[x - s]], lf[x - (1 << lg[x - s]) + 1][lg[x - s]]);
    db r = min(rg[s + 1][lg[x - s]], rg[x - (1 << lg[x - s]) + 1][lg[x - s]]);
    return l < r && r > b[s] && l < b[s] + 1;
}

C++(clang++11) 解法, 执行用时: 90ms, 内存消耗: 39944K, 提交时间: 2021-05-10 17:59:19

#include <bits/stdc++.h>
#define maxn 100086

using namespace std;

struct Frac{
	int x, y;
	
	Frac(){}
	
	Frac(int xx, int yy){
		int gcd = __gcd(xx, yy);
		x = xx / gcd, y = yy / gcd; 
	}
	
	bool operator < (const Frac &f) const {
		return 1ll * x * f.y < 1ll * y * f.x;
	}
	
};

int n;
int a[maxn];
Frac mn[maxn][25], mx[maxn][25];

int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++) scanf("%d", &a[i]);
	for(int i = 2;i <= n;i++) mn[i][0] = Frac(a[i], a[i - 1] + 1), mx[i][0] = Frac(a[i] + 1, a[i - 1]);
	for(int j = 1;j <= 20;j++){
		for(int i = 2;i + (1 << j) - 1 <= n;i++){
			mn[i][j] = max(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
			mx[i][j] = min(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
		}
	} 
	int ans = 1;
	for(int i = 1;i < n;i++){
		int x = i + 1;
		Frac l(a[i], 1), r(a[i] + 1, 1);
		for(int j = 20;~j;j--){
			if(x + (1 << j) - 1 > n) continue;
			Frac L = max(l, mn[x][j]), R = min(r, mx[x][j]);
			if(!(L < R)) continue;
			l = L, r = R, x += 1 << j;
		}
		ans = max(ans, x - i);
	}
	printf("%d", ans);
}