首先油价是大于0的,油箱是无限的。因此我们不会从油价低的地方到油价高的地方去加油。我们可以根据每个地方油价的从高到低依次更新。
考虑某次到达点t后,其油价是v,那么对另一点s的贡献是v*abs(t-s)。这是两条直线。
考虑到我们是动态的确定点,并添加直线,因此维护下凸壳即可。
使用线段添加的李超树,复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define lson rt * 2
#define rson rt * 2 + 1
typedef long long ll;
const int N = 1e5 + 100;
int n, s, t, tp, cnt;
int has[N], val[N];
ll dp[N];
struct Line {
ll k, b;
Line() { k = 0; b = 1e18; }
Line(ll k, ll b) :k(k), b(b) {}
ll cal(ll x) {
return k * x + b;
}
}tree[N * 4];
void insert(Line x, int l, int r, int rt) {
int m = (l + r) / 2;
if (tree[rt].cal(has[m]) > x.cal(has[m])) swap(tree[rt], x);
if (l == r) return;
if (tree[rt].cal(has[l]) > x.cal(has[l])) insert(x, l, m, lson);
else insert(x, m + 1, r, rson);
}
void insert(int rl, int rr, Line x, int l, int r, int rt) {
if (rl == l && rr == r) return void(insert(x, l, r, rt));
int m = (l + r) / 2;
if (rr <= m) insert(rl, rr, x, l, m, lson);
else if (m < rl) insert(rl, rr, x, m + 1, r, rson);
else {
insert(rl, m, x, l, m, lson);
insert(m + 1, rr, x, m + 1, r, rson);
}
}
void query(int id, Line &res, int l, int r, int rt) {
if (tree[rt].cal(has[id]) < res.cal(has[id])) res = tree[rt];
if (l == r) return;
int m = (l + r) / 2;
if (id <= m) query(id, res, l, m, lson);
else query(id, res, m + 1, r, rson);
}
struct node {
int w, id;
}sa[N];
bool operator < (node a, node b) {
return a.w > b.w;
}
int get(int id) {
return lower_bound(has + 1, has + tp + 1, id) - has;
}
int main() {
//freopen("0.txt", "r", stdin);
scanf("%d%d%d", &n, &s, &t);
for (int i = 1; i <= n; i++) scanf("%d%d", &sa[i].w, &sa[i].id), has[++tp] = sa[i].id;
has[++tp] = s; has[++tp] = t;
sort(has + 1, has + tp + 1);
tp = unique(has + 1, has + tp + 1) - has - 1;
memset(val, 0x3f3f3f3f, sizeof(val));
s = get(s); t = get(t);
for (int i = 1; i <= n; i++) {
sa[i].id = get(sa[i].id);
val[sa[i].id] = min(val[sa[i].id], sa[i].w);
if (sa[i].id == s) sa[i].w = 0;
}
sort(sa + 1, sa + n + 1);
insert(s, tp, Line(val[s], -1LL * has[s] * val[s]), 1, tp, 1);
insert(1, s, Line(-val[s], 1LL * has[s] * val[s]), 1, tp, 1);
for (int i = 1; sa[i].w; i++) {
if (sa[i].w != val[sa[i].id]) continue;
Line res; int id = sa[i].id;
query(id, res, 1, tp, 1);
dp[id] = res.cal(has[id]);
insert(1, id, Line(-val[id], dp[id] + 1LL * has[id] * val[id]), 1, tp, 1);
insert(id, tp, Line(val[id], dp[id] - 1LL * has[id] * val[id]), 1, tp, 1);
}
Line res;
query(t, res, 1, tp, 1);
printf("%lld\n", res.cal(has[t]));
return 0;
}
我们通常衡量一个Web系统的吞吐率的指标是QPS(Query Per Second,每秒处理请求...
H5支付是指商户在微信客户端外的移动端网页展示商品或服务,用户在前述页面确认...
1,父传子 子组件中定义 props 字段,类型为数组(如果需要限制字段值类型,也可...
先看代码 复制代码 代码如下: div style="position:relative; width:[flash的宽]...
详解 Spring注解的(ListMap)特殊注入功能 最近接手一个新项目,已经没有原开发...
本文转载自微信公众号「 jinjunzhu」,作者 jinjunzhu 。转载本文请联系 jinjunz...
OBJECT ID="agobjOraSession" RUNAT="Server" PROGID="OracleInProcServer.XOraS...
XML/HTML Code 复制内容到剪贴板 input id = username name = username type = t...
CentOS版本:7.6.1810 3台 JDK版本:1.8.0_191 Zookeeper版本:3.4.10 安装包 链接h...
0x01 Mysql Mysql划分:权限 root 普通用户 版本 mysql5.0 mysql5.0 1.1 root权...