第一道决策单调性……
题目描述
题目分析
挺好的……模板题？
寄存了先。
1 #include<bits/stdc++.h> 2 typedef long long ll; 3 const int maxn = 100035; 4 5 struct node 6 { 7 int x,l,r; 8 node(int a=0, int b=0, int c=0):x(a),l(b),r(c) {} 9 }; 10 int n,k,a[maxn],g[maxn]; 11 ll s[maxn],mid,pos,ans,f[maxn]; 12 std::deque<node> q; 13 14 int read() 15 { 16 char ch = getchar(); 17 int num = 0; 18 bool fl = 0; 19 for (; !isdigit(ch); ch=getchar()) 20 if (ch=='-') fl = 1; 21 for (; isdigit(ch); ch=getchar()) 22 num = (num<<1)+(num<<3)+ch-48; 23 if (fl) num = -num; 24 return num; 25 } 26 void clears(std::deque<node> &q) 27 { 28 std::deque<node> emt; 29 std::swap(q, emt); 30 } 31 ll val(int l, int r) 32 { 33 if (l >= r) return 0; 34 int mid = (l+r)>>1; 35 return 1ll*(mid-l+1)*a[mid]-(s[mid]-s[l-1])+(s[r]-s[mid-1])-1ll*(r-mid+1)*a[mid]; 36 } 37 ll calc(int l, int r) 38 { 39 return f[l]+val(l+1, r); 40 } 41 bool check(ll w) 42 { 43 clears(q), q.push_front(node(0, 1, n)); 44 for (int i=1; i<=n; i++) 45 { 46 // printf("w:%lld i:%d ",w,i); 47 node tt = q.front(); 48 g[i] = g[tt.x]+1, f[i] = calc(tt.x, i)+w; 49 int upd = -1; 50 while (q.size()) 51 { 52 node tt = q.back(); 53 if (calc(tt.x, tt.l) > calc(i, tt.l)) 54 upd = tt.l, q.pop_back(); 55 else{ 56 int lbd = tt.l, rbd = tt.r, fnd = -1; 57 while (lbd <= rbd) 58 { 59 int mid = (lbd+rbd)>>1; 60 if (calc(tt.x, mid) > calc(i, mid)) 61 fnd = mid, rbd = mid-1; 62 else lbd = mid+1; 63 } 64 if (fnd!=-1) upd = fnd, q.back().r = fnd-1; 65 break; 66 } 67 } 68 if (upd!=-1) q.push_back(node(i, upd, n)); 69 if (q.size()){ 70 q.front().l++; 71 if (q.front().l > q.front().r) q.pop_front(); 72 } 73 } 74 return g[n] <= k; 75 } 76 int main() 77 { 78 n = read(), k = read(); 79 if (k >= n) puts("0"); 80 else{ 81 for (int i=1; i<=n; i++) a[i] = read(); 82 std::sort(a+1, a+n+1); 83 for (int i=1; i<=n; i++) s[i] = s[i-1]+a[i]; 84 ll l = 0, r = 1e12; 85 for (; l<=r; ) 86 { 87 mid = (l+r)>>1; 88 if (check(mid)) 89 ans = f[n]-mid*k, r = mid-1; 90 else l = mid+1; 91 } 92 printf("%lld ",ans); 93 } 94 return 0; 95 }
END