Bzoj3203: [Sdoi2013]保护出题人凸包 + 三分

题目描述

出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。

参加SDOI2012的小朋友们释放出大量的僵尸，企图攻击铭铭的家。而你作为SDOI2013的参赛者，你需要保护出题人铭铭。

僵尸从唯一一条笔直道路接近，你们需要在铭铭的房门前放置植物攻击僵尸，避免僵尸碰到房子。

第一关，一只血量为 $a1a_1a1 点的墦尸从距离房子 x1x_1x1 米处速接近，你们放置了攻击力为 y1y_1y1 点/秒的植物进行防御；第二关，在上一关基础上，僵尸队列排头增加一只血量为 a2a_2a2 点的僵尸，与后一只僵尸距离 ddd 米，从距离房 x2x_2x2 米处匀速接近，你们重新放置攻击力为 y2y_2y2 点/秒的植物；……；第 nnn 关，僵尸队列共有 nnn 只僵尸，相邻两只僵尸距离 ddd 米，排头僵尸血量为 ana_nan 点，排第二的僵尸血量 an−1a_{n-1}an−1 ，以此类推，排头僵尸从距离房子 xnx_nxn 米处匀速接近，其余僵尸跟随排头同时接近，你们重新放置攻击力为 yny_nyn 点/秒的植物。$

每只僵尸直线移动速度均为

游戏得分取决于你们放置的植物攻击力的总和 $_{i=1} ^{n} y_ii=1∑nyi ，和越小分数越高，为了追求分数上界，你们每关都要放置攻击力尽量小的植物。$

作为SDOI2013的参赛选手，你们能保护出题人么？

输入输出格式

输入格式：

第一行两个空格隔开的正整数n和d，分别表示关数和相邻僵尸间的距离。

接下来n行每行两个空格隔开的正整数，第i + 1行为Ai和 Xi，分别表示相比上一关在僵尸队列排头增加血量为Ai 点的僵尸，排头僵尸从距离房子Xi米处开始接近。

输出格式：

一个数，n关植物攻击力的最小总和，保留到整数。

输入输出样例

输入样例#1：

输出样例#1：

说明

第一关：距离房子3米处有一只血量3点的僵尸，植物最小攻击力为1.00000；
第二关：距离房子1米处有一只血量1点的僵尸、3米处有血量3点的僵尸，植物最小攻击力为1.33333；
第三关：距离房子8米处有一只血量10点的僵尸、10米处有血量1点的僵尸、12米处有血量3点的僵尸，植物最小攻击力为1.25000；
第四关：距离房子8米处有一只血量4点的僵尸、10米处有血量10点的僵尸、12米处有血量1点的僵尸、14米处有血量3点的僵尸，植物最小攻击力为1.40000；
第五关：距离房子3米处有一只血量2点的僵尸、5米处有血量4点的僵尸、7米处有血量10点的僵尸、9米处有血量1点的僵尸、11米处有血量3点的僵尸，植物最小攻击力为2.28571。
植物攻击力的最小总和为7.26905。

对于100%的数据， 1<=n<=10^5，1<=d<=10^12,1<=x<= 10^12,1<=a<=10^12

提交地址： bzoj3203；Luogu3299

题面看的一脸懵逼，一副不可做的样子；

因为当时翻看各种题解并没有懂，所以决定写一篇较为详细的题解，让不会的小伙伴们更快的理解，少走弯路；

题面不解释，玩过植物大战僵尸的都理解(没有玩过现在去)；

由简单的分析，我们可以得到， f[i] = max((sum[i] - sum[j-1]) / (d *(i - j) + x[i]))， f[i]表示第i关的最小需要的攻击力；

很清晰？就是j到i的所有僵尸的生命值之和，除以第j个僵尸到你的距离，结果不就是攻击力嘛，最后求max(因为对于每个僵尸j都不能让他走到你跟前)，美滋滋；

O(n^2)妥妥的50分，但问题来了, 我们可是要AK的人；

仔细看看刚才的方程，你想到了什么？斜率！！！

我们令X1 = d * i + x[i], Y1 = sum[i], Y2 = sum[j-1], X2 = d *j;

我们可以用单调栈维护一个右下凸壳，维护(sum[i-1] - sum[j-1]) / (d * i - d * j)，为什么要这么维护？

我们考虑之前的式子，我们的i在求它的时候是不变的，所以我们把i想象成一个定点，令i的坐标为(d * i + x[i], sum[i]);

然后我们加入点i，我们要求的攻击力其实就是i和当前凸包上的点的斜率最大值；

因为sum[i](点i的纵坐标) - sum[j-1](凸包上维护的点的纵坐标) = sum[i] - sum[j-1](要求的式子的上半边)；

d * i + x[i](点i的横坐标) - d *j (凸包上维护的点的横坐标) = d *(i - j) + x[i](要求的式子的下半边);

刚好满足！！！！

哇塞我们好像有O（n）的方法了！！

然而是ma？

我们好像还要求点i与凸包上的点的斜率最大值！

哦...这不是熟悉的三分法求凸函数极值的变式嘛！

所以加上用三分，总复杂度O(nlogn?);

稳！！！

对了这道题要用long long，别怪我没提醒你，要不打死都想不出来；

最后奉上代码（码风奇特切勿吐槽）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cctype>
#include <cmath>
using namespace std;
#define int long long

inline char nc()
{
    static const int BS = 1 << 22;
    static unsigned char buf[BS], *st, *ed;
    if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);
    return st == ed ? EOF : *st++;
}
#define nc getchar
inline int read()
{
    int ch = nc();
    int res = 0;
    bool flag = 0;
    while (!isdigit(ch)) 
    {
        if (ch == '-') flag = 1;
        ch = nc();
    }
    while (isdigit(ch))
    {
        res = (res << 3) + (res << 1) + (ch - '0');
        ch = nc();
    }
    return flag ? -res : res;
}

const int N = 1e5+5;
#define eps 1e-6
#define lldou long double

int n, d;
int dis[N], sum[N];

inline int X1(int i)
{
    return d * i + dis[i];
}

inline int Y1(int i)
{
    return sum[i];
}

inline int X2(int i)
{
    return d * i;
}

inline int Y2(int i)
{
    return sum[i-1];
}

inline long double slope1(int i, int j)
{
    return (double)((double)(Y2(i) - Y2(j)) / (double)(X2(i) - X2(j)));/* - dis[i]*/
}

inline long double slope(int i, int j)
{
    return (double)((double)(Y1(i) - Y2(j)) / (double)(X1(i) - X2(j)));
}

int sta[N], top; // 单调栈 

signed main()
{
    n = read(), d = read();
    
    for (register int i = 1 ; i <= n ; i ++)
    {
        int x = read();
        sum[i] = sum[i-1] + x;
        dis[i] = read();
    }
    
    lldou ans = 0.0;
    
    for (register int i = 1 ; i <= n ; i ++)
    {
        while (top > 1 and slope1(i, sta[top]) <= slope1(sta[top], sta[top-1])) top--;
        sta[++top] = i;
        int l = 1, r = top, mid1, mid2;
        while (l < r)
        {
            mid1 = (l + r + l) / 3;
            mid2 = (r + r + l) / 3;
            if (mid1 == mid2) break;
            if (slope(i, sta[mid1]) > slope(i, sta[mid2])) r = mid2 - 1;
            else l = mid1 + 1;
        }
        ans += (lldou)max(slope(i, sta[l]), slope(i, sta[r]));
    //    printf("%Lf
", (lldou)max(slope(i, sta[l]), slope(i, sta[r])));
    }
    
    printf("%.0Lf
", ans);
    return 0;
}

转载请注明出处谢谢谢谢