50分,求助神佬们
查看原帖
50分,求助神佬们
542879
_HCl_楼主2022/5/25 23:23
#include<bits/stdc++.h>
using namespace std;
int n;
int q[1000001];
long double c[1000001];
long long f[1000001];
struct xzh{
    int w,h;
}a[1000001];
long double calc(int aa,int b){
    return (long double)(f[b-1]-f[aa-1])/(a[aa].h-a[b].h);
}
bool cmp(xzh x,xzh y){
    return x.h>y.h||(x.h==y.h&&x.w>y.w);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i].w>>a[i].h;
    sort(a+1,a+n+1,cmp);
    int j=1,t=0,h=1;
    for(int i=1;i<=n;++i)if(a[j].w<a[i].w)a[++j]=a[i];
    for(int i=1;i<=j;++i)
    {
        while(h<t&&c[t-1]>=calc(q[t],i))t--;
        c[t]=calc(q[t],i);
        q[++t]=i;
        while(h<t&&c[h]<=a[i].w)h++;
        f[i]=(a[q[h]].h*a[i].w+f[q[h]-1]);
    }
    printf("%lld",f[j]);
 } 

WA了5个点,好像爆负数了,但里边变量应该都开够了

2022/5/25 23:23
加载中...