题目
思路
首先按照(t)排序！！！！
首先考虑一个暴力(dp)
用(f[i])表示前(i)个人到达地点所需要的时间。
那么就有如下的转移
[f_i = min_{1 le j le i}(max(f_j,t_i) + max{w_{j + 1} ... w_i} * 2)
]
这样复杂度是(o(n^2))的
考虑优化上面的(dp)
因为已经按照(t)从小到大排过序了，所以如果(w_i le w_{i + 1})那么第(i)这个人就一定是和第(i+1)个人一起跟优秀。所以就可以把第(i)人剔除掉。
用单调栈可以完成上面的工作。
现在就变成了一个(t)单调递增，(w)单调递减的序列
然后再去看上面的(dp)，我们可以把它分成两段。
(if(f_j le t_i))
[f_i=t_i + max{w_{j+1}...w_i} * 2
]
(if(f_j > t_i))
[f_i = f_j + max{w_{j+1}...w_i} * 2
]
因为(w)数组单减，所以上面的式子(max{w_{j+1}...w_i})是肯定是(w_{j+1})。
所以上面的(dp)式子可以这样写
(if(f_j le t_i))
[f_i=t_i + w_{j+1} * 2
]
(if(f_j > t_i))
[f_i = f_j + w_{j+1} * 2
]
因为(f)数组是递增的，所以第一种转移肯定一前一部分，第二种转移是后一部分。可以找到他们的分界点(p)
对于(p)及(p)之前的，因为(t_i)固定了，所以只要找到最小的(w_{j + 1})就行了。显然(w_{p+1})最小
对于(p)之后的，就是要找最小的(f_j+w_{j+1}*2)，用线段树维护一下。
代码
/*
* @Author: wxyww
* @Date: 2019-03-24 19:59:19
* @Last Modified time: 2019-03-24 20:43:41
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const ll INF = 4e9,N = 1000000 + 100;
#define int ll
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int b[N],top,tree[N << 2], f[N];
struct node {
int p,w;
}a[N];
void update(int rt,int l,int r,int pos,int c) {
if(l == r) {
tree[rt] = c;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) update(rt << 1,l,mid,pos,c);
else update(rt << 1 | 1,mid + 1,r,pos,c);
tree[rt] = min(tree[rt << 1],tree[rt << 1 | 1]);
}
int query(int rt,int l,int r,int L,int R) {
if(L <= l && R >= r) return tree[rt];
int mid = (l + r) >> 1;
int ans = INF;
if(L <= mid) ans = min(ans,query(rt << 1,l,mid,L,R));
if(R > mid) ans = min(ans,query(rt << 1 | 1,mid + 1,r,L,R));
return ans;
}
bool cmp(const node &A,const node &B) {
return A.p < B.p;
}
signed main() {
int n = read();
for(int i = 1;i <= n;++i) a[i].p = read(),a[i].w = read();
sort(a + 1,a + n + 1,cmp);
for(int i = 1;i <= n;++i) {
while(a[i].w >= a[b[top]].w && top) top--;
b[++top] = i;
}
int p = 0;
for(int i = 1;i <= top;++i) {
while(p < i - 1 && f[p + 1] <= a[b[i]].p) ++p;
f[i] = a[b[i]].p + a[b[p + 1]].w * 2;
if(p + 1 <= i - 1) f[i] = min(f[i],query(1,1,top,p + 1,i - 1));
update(1,1,top,i,f[i] + a[b[i + 1]].w * 2);
}
cout<<f[top];
return 0;
}