第一道决策单调性……
题目描述
题目分析
挺好的……模板题?
寄存了先。
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = ; struct node
{
int x,l,r;
node(int a=, int b=, int c=):x(a),l(b),r(c) {}
};
int n,k,a[maxn],g[maxn];
ll s[maxn],mid,pos,ans,f[maxn];
std::deque<node> q; int read()
{
char ch = getchar();
int num = ;
bool fl = ;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = ;
for (; isdigit(ch); ch=getchar())
num = (num<<)+(num<<)+ch-;
if (fl) num = -num;
return num;
}
void clears(std::deque<node> &q)
{
std::deque<node> emt;
std::swap(q, emt);
}
ll val(int l, int r)
{
if (l >= r) return ;
int mid = (l+r)>>;
return 1ll*(mid-l+)*a[mid]-(s[mid]-s[l-])+(s[r]-s[mid-])-1ll*(r-mid+)*a[mid];
}
ll calc(int l, int r)
{
return f[l]+val(l+, r);
}
bool check(ll w)
{
clears(q), q.push_front(node(, , n));
for (int i=; i<=n; i++)
{
// printf("w:%lld i:%d\n",w,i);
node tt = q.front();
g[i] = g[tt.x]+, f[i] = calc(tt.x, i)+w;
int upd = -;
while (q.size())
{
node tt = q.back();
if (calc(tt.x, tt.l) > calc(i, tt.l))
upd = tt.l, q.pop_back();
else{
int lbd = tt.l, rbd = tt.r, fnd = -;
while (lbd <= rbd)
{
int mid = (lbd+rbd)>>;
if (calc(tt.x, mid) > calc(i, mid))
fnd = mid, rbd = mid-;
else lbd = mid+;
}
if (fnd!=-) upd = fnd, q.back().r = fnd-;
break;
}
}
if (upd!=-) q.push_back(node(i, upd, n));
if (q.size()){
q.front().l++;
if (q.front().l > q.front().r) q.pop_front();
}
}
return g[n] <= k;
}
int main()
{
n = read(), k = read();
if (k >= n) puts("");
else{
for (int i=; i<=n; i++) a[i] = read();
std::sort(a+, a+n+);
for (int i=; i<=n; i++) s[i] = s[i-]+a[i];
ll l = , r = 1e12;
for (; l<=r; )
{
mid = (l+r)>>;
if (check(mid))
ans = f[n]-mid*k, r = mid-;
else l = mid+;
}
printf("%lld\n",ans);
}
return ;
}
END