首先题目中的贡献式子
$$\frac{(A_i - A_j)B_iB_j}{2A_iA_j}$$

化简得$\frac{1}{2}(B_i\frac{B_j}{A_j}-B_j\frac{B_i}{A_i})$

发现可以看成一个向量叉积,转成面积,再观察题目中的特殊性质$B_i$先单调不降,再单调不增,看上去就联想到做一个凸包,使得面积最大(权值越大,得解

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 100010
using namespace std;
struct point{
    double x,y;
    point operator-(const point &a){
        return (point){x-a.x,y-a.y};
    }
    point operator+(const point &a){
        return (point){x+a.x,y+a.y};
    }
    friend bool operator<(point a,point b){
        return a.x<b.x||(a.x==b.x&&a.y<b.y);
    }
}p[maxn],st[maxn];
double operator^(point a,point b){
    return a.x*b.y-b.x*a.y;
}
double dist(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int n,a[maxn],b[maxn];
double calc(point a,point b,point c){
    return (b-a)^(c-a);
}
void init(){
    scanf("%d",&n);
    int sum=0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=(sum+=a[i]);
    for(int i=1;i<=n;i++){
       p[i]=(point){(double)b[i],(double)b[i]*1.0/(double)a[i]};
    }
    sort(p+1,p+n+1);
    int top=0;
    for(int i=1;i<=n;i++){
        while(top>1&&calc(st[top-1],st[top],p[i])<=0) top--;//保证了单调性 后面=0的肯定比前面长 
        st[++top]=p[i];
    }
    int tmp=top;
    for(int i=n-1;i>=1;i--){
        while(top>tmp&&calc(st[top-1],st[top],p[i])<=0) top--;
        st[++top]=p[i]; 
    }
    double ans=0;
    for(int i=2;i<=top;i++){
        ans+=(st[i-1]^st[i])/2;
    }
    printf("%.5f",ans);
}
int main(){
    init();
    
    return 0;
}
Last modification:February 15th, 2019 at 10:04 pm