题目传送门:http://codeforces.com/contest/957/problem/D
题意大致是这样的:有一个水池,每天都有一个水位(一个整数)。每天都会在这一天的水位上划线(如果这个水位已经被划线了,那么不划线)。
现在告诉你每天能看见的线条mi(就是高于水面的,刚好在水面的不算),设di为第i天水面以下的线条数(刚好在水面的不算),求(d1+d2+d3....dn)的最小值。
解析:
我们设第i天有ki条水位线,容易得到:
移项后,将d留在右边,我们发现mi和n都是固定的,所以,我们要让ki尽量小,此时,聪明的你一定想到了不等式。
我们发现:
我们先对m进行排序,从大到小对b(k的最小值)不断更新。
第二遍,我们从1到n扫一遍b,如果
那么将答案答案加上
具体看代码:(PS:博主最近想表白,祝我成功)
#include <bits/stdc++.h> using namespace std; #define _l long long +; int n,a[N],b[N]; _l ans=; bool flg[N]; struct T{int x,p;}h[N]; bool cmp(T A,T B){return A.x<B.x;} int main(){ scanf("%d",&n); ;_l sig=; ;i<=n;i++)scanf(; sort(h+,h++n,cmp); ;i--)b[h[i].p-]=max(b[h[i].p-],h[i].x); ;--i)b[i-]=max(b[i-],b[i]-); ;i<n;++i)b[i+]=max(b[i+],b[i]); ;i<=n;i++){ ; ){ tmp=a[i]+;flg[i]=;b[i]=;ans+=b[i];continue; } if(flg[i]){ b[i]=max(b[i],b[i-]+a[i]-tmp+); }]);tmp=max(tmp,b[i]); ans+=b[i]; } printf("%I64d",ans-(_l)n-sig); }