codeforces round 472(DIV2)D Riverside Curio题解(思维题)

时间:2021-10-13 10:36:26

题目传送门:http://codeforces.com/contest/957/problem/D

题意大致是这样的:有一个水池,每天都有一个水位(一个整数)。每天都会在这一天的水位上划线(如果这个水位已经被划线了,那么不划线)。

现在告诉你每天能看见的线条mi(就是高于水面的,刚好在水面的不算),设di为第i天水面以下的线条数(刚好在水面的不算),求(d1+d2+d3....dn)的最小值。

解析:

我们设第i天有ki条水位线,容易得到:codeforces round 472(DIV2)D Riverside Curio题解(思维题)

移项后,将d留在右边,我们发现mi和n都是固定的,所以,我们要让ki尽量小,此时,聪明的你一定想到了不等式。

我们发现:codeforces round 472(DIV2)D Riverside Curio题解(思维题)

我们先对m进行排序,从大到小对b(k的最小值)不断更新。

第二遍,我们从1到n扫一遍b,如果codeforces round 472(DIV2)D Riverside Curio题解(思维题)

那么将答案答案加上codeforces round 472(DIV2)D Riverside Curio题解(思维题)

具体看代码:(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);
}