洛谷 P9936 [NFLSPC #6] 等差数列-526互联

对 \((i, a_i)\) 求出下凸包，那么一条凸包的斜率非正的切线是候选答案。

只考虑切凸包上第 \(i\) 个点的切线，那么斜率的左边界是过凸包第 \(i\) 和第 \(i + 1\) 个点的直线斜率，右边界是过凸包第 \(i - 1\) 和第 \(i\) 个点的直线斜率。最优方案的切线斜率一定要么贴着左边界，要么贴着右边界，分类取个 \(\max\) 即可。

注意斜率要是整数，上/下取整处理一下即可。

时间复杂度 \(O(n)\)。

code

// Problem: P9936 [NFLSPC #6] 等差数列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9936
// Memory Limit: 1 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;

ll n, a[maxn], stk[maxn], top;
struct node {
	ll x, y;
	node(ll a = 0, ll b = 0) : x(a), y(b) {}
} b[maxn];

inline node operator + (const node &a, const node &b) {
	return node(a.x + b.x, a.y + b.y);
}

inline node operator - (const node &a, const node &b) {
	return node(a.x - b.x, a.y - b.y);
}

inline ll operator * (const node &a, const node &b) {
	return a.x * b.y - a.y * b.x;
}

inline ll f(ll n) {
	return n * (n + 1) / 2;
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		b[i] = node(i, a[i]);
	}
	top = 0;
	for (int i = 1; i <= n; ++i) {
		while (top >= 2 && (b[stk[top]] - b[stk[top - 1]]) * (b[i] - b[stk[top - 1]]) >= 0) {
			--top;
		}
		stk[++top] = i;
	}
	ll ans = 1e18;
	for (int i = 1; i <= top; ++i) {
		ldb l = -1.1e9, r = 0;
		if (i > 1) {
			r = min(r, (ldb)(b[stk[i]].y - b[stk[i - 1]].y) / (b[stk[i]].x - b[stk[i - 1]].x));
		}
		if (i < top) {
			l = max(l, (ldb)(b[stk[i]].y - b[stk[i + 1]].y) / (b[stk[i]].x - b[stk[i + 1]].x));
		}
		for (ll x = ceil(l); x <= r && x - l <= 2; ++x) {
			ans = min(ans, a[stk[i]] * n - x * f(stk[i] - 1) + x * f(n - stk[i]));
		}
		for (ll x = floor(r); x >= l && r - x <= 2; --x) {
			ans = min(ans, a[stk[i]] * n - x * f(stk[i] - 1) + x * f(n - stk[i]));
		}
	}
	for (int i = 1; i <= n; ++i) {
		ans -= a[i];
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}