CF377E Cookie Clicker

· · 题解

建议标签:凸包

思路:

看到最少秒数,我们能想到满足二分性质,因为如果一个时间点之前的可以那么之后的也一定可以

发现我们check函数有一个n^2的做法:dp_{i,j}表示记录第i秒我们当且在使用j工厂,能有的最大金币数,这样肯定TLE...

但是看到这个动态规划的形式,其实很容易发现是维护了许多直线,但是只有他们构成的凸包有用处

于是想:我们把time(每一秒)当做x轴,value(手上的钱)当做y轴的话,连续选择一个工厂生产就相当于在某个点开始的一条射线,而且那个点的y>C_i而且射线斜率是V_i

然后会发现我们要确定那个点,其实就是在确定最优决策下达到C_i的最短时间!

所以我们就是要对这些个直线按照C_i 递增的顺序依次进行处理,计算他们的最优代价,因为我们一定先解锁代价小的再解锁代价大的

做法:

开一个栈维护我们最优决策构成的凸包

对于一条新的要加入的直线,从栈底开始向上扫,找到第一条包括大于他的纵坐标的点的直线,即下图中的红点即其所在直线,注意可能红点的纵坐标不是C_i,但一定大于C_i:

然后我们可以根据那个点,相应的计算出蓝线的表达式

我们再把蓝线插入凸包即可qwq

由于我们其中C_i是递增的,每次只用在栈顶栈底操作,所以维护凸包的复杂度是O(n)的

瓶颈在于排序O(nlogn)


//From Dawn light
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18;
const int MAXN = 3e5 + 7;
int n, ans;
int S, head, tail;
int f[MAXN], que[MAXN];
struct Mac {
    int V, C;
    bool operator<(const Mac &x)const {
        return C == x.C ? V < x.V : C < x.C;
    }
} a[MAXN];

int calc(int x, int o) {
    return max(0ll, (x - f[o] + a[o].V - 1) / a[o].V);
}

bool chk(int i, int j, int V) {
    int Xi = calc(V, i);
    int Xj = calc(V, j);
    if(Xi != Xj)return Xi > Xj;
    return f[i] + Xi * a[i].V <= f[j] + Xj * a[j].V;
}

int getslope(int i, int j) {
    return (f[i] - f[j]) / (a[j].V - a[i].V);
}

signed main() {
    // freopen("test.in", "r", stdin);
    scanf("%lld%lld", &n, &S);
    for(int i = 1; i <= n; ++i)scanf("%lld%lld", &a[i].V, &a[i].C);
    sort(a + 1, a + n + 1);
    int h = 1, t = 0, V = 0;
    ans = inf;
    for(int i = 1; i <= n; ++i) {
        if(a[i].V <= V)continue;
        V = a[i].V;
        while(h < t && chk(que[h], que[h + 1], a[i].C))++h;
        if(i > 1) {
            int j = que[h];
            f[i] = f[j] - a[i].C - calc(a[i].C, j) * (a[i].V - a[j].V);
        }
        ans = min(ans, calc(S, i));
        while(h < t && getslope(que[t - 1], que[t]) >= getslope(que[t], i))
            --t;
        que[++t] = i;
    }
    printf("%lld\n", ans);
    return 0;
}