T1 美丽的子区间
还行吧,根据大眼观察法 可以看出当 \(x\) 为使用科技的次数时,函数 \(f(x)\) 等于使用 \(x\) 次科技的最小答案是一个单谷函数,可以三分,注意到使用 \(x\) 次科技的时候的第 \(i\) 个数的答案是 \(\min \limits_{j=\min(1,i-x+1)}^{i}\)。而且还要加上一个小贪心:把最小的放在最前面。
#include <fstream>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 1e5 + 1;
ifstream cin("collect.in");
ofstream cout("collect.out");
ll n, k, o[kMaxN], a[kMaxN], s[kMaxN];
struct ST {
static const int kMaxN = 2e5 + 5;
ll n, log2[kMaxN], Maxn[kMaxN][20], Minn[kMaxN][20];
ST() {}
ST(ll n, ll a[]) {
memset(Minn, 0x3f, sizeof(Minn));
for (int i = 1; i <= n; i++) {
Minn[i][0] = Maxn[i][0] = a[i];
}
for (int i = 2; i <= n; i++) {
log2[i] = log2[i / 2] + 1;
}
for (int j = 1; j < 20; j++) {
for (int i = 1; i + (1 << j - 1) <= n; i++) {
Maxn[i][j] = max(Maxn[i][j - 1], Maxn[i + (1 << j - 1)][j - 1]);
Minn[i][j] = min(Minn[i][j - 1], Minn[i + (1 << j - 1)][j - 1]);
}
}
}
ll Max(int l, int r) {
int len = r - l + 1;
return max(Maxn[l][log2[len]], Maxn[r - (1 << log2[len]) + 1][log2[len]]);
}
ll Min(int l, int r) {
int len = r - l + 1;
return min(Minn[l][log2[len]], Minn[r - (1 << log2[len]) + 1][log2[len]]);
}
} st;
ll F(ll x) {
ll ans = x * k;
for (int i = 1; i <= n; i++) {
ll o = st.Min(max(1ll, i - x), i);
ans += o;
}
return ans;
}
int main() {
cin >> n >> k;
ll minn = 1e9, pos;
for (int i = 1; i <= n; i++) {
cin >> o[i];
if (minn > o[i]) {
pos = i;
minn = o[i];
}
}
for (int i = pos; i <= n; i++) {
a[i - pos + 1] = o[i];
}
for (int i = 1; i < pos; i++) {
a[i + (n - pos + 1)] = o[i];
}
st = ST(n, a);
ll l = 0, r = n - 1;
while (l < r) {
ll mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
ll ans1 = F(mid1), ans2 = F(mid2);
if (ans1 > ans2) {
l = mid1 + 1;
} else {
r = mid2 - 1;
}
}
ll ans = 1e18;
for (int i = max(0ll, l - 2); i <= min(n, r + 2); i++) {
ans = min(ans, F(i));
}
cout << ans << '\n';
return 0;
}
标签:总结,minn,Minn,int,ll,kMaxN,ST,10.10
From: https://www.cnblogs.com/GenesisCrystal/p/18457704