壹、题目描述 ¶
贰、题解 ¶
真的一个脑瘫题，我还往线段树优化建图想......
首先注意到，其实从哪个点出发都一样，因为我们最后反正要走一个哈密顿回路出来。
我们得将 \(\max\{c_i,a_j-a_i\}\) 改写一下，有
\[\max\{c_i,a_j-a_i\}=c_i+\max\{0,a_j-a_i-c_i\} \]由于我们每个点都要经过一次，所以我们可以先忽略 \(c_i\)，最后将答案加上 \(\sum c_i\) 即可。
现在我们想要最小化 \(\max\{0,a_j-a_i-c_i\}\).
首先可以将原序列按照 \(a_i\) 升序排列，然后我们就有了两种解法。
§ 建图最短路 §
一定有 \(j\rightarrow i(j>i)\) 的花费为 \(0\)，所以我们就有了第一种边：连接所有 \(i+1\rightarrow i\)，权值为 \(0\).
不仅仅这种边是免费的，还有 \(a_j-a_i-c_i\le 0\) 的边。
本来我们需要连接所有这样的、满足条件的点对，但是由于第一种边的存在，我们只需要连接最大的 \(a_j\) 的点，就可以覆盖所有的点了，而这个最大的 \(j\) 怎么找呢？二分查找是个好办法！
但是我们还要走付费边啊，我们找到了 \(j\)，那么从 \(i\rightarrow j+1\) 的就得是付费边了吧，我们将这样付费相邻的点串起来，就达到了类似第一种边的效果。这是第三种边。
把这三种边全部连起来，直接上 \(\tt dijkstra\) 就行了。
§ 左右端点想法 §
将 \(a_i\) 排序之后，答案就是：
\[\sum_{i=2}^n\max\{0,a_i-\max_{j<i}\{a_j+c_j\}\} \]这很简单吧？但是为什么是这样的啊？对于 \(i\)，我们将其看作 \(\lang l_i,r_i\rang=[a_i,a_i+c_i]\) 的区间，那么问题就抽象为：从区间 \(i\) 走到 \(j\)，你需要花费的是 \(\max\{0,l_j-r_i\}\)，也就是后一个区间的左端点和前一个区间的右端点的差值，或者 \(0\)，问经过所有区间的最小花费，将区间按照左端点排序之后，最优的就是从最大的右端点开始走，走到下一个区间，而从最后一个区间走回 \(1\) 呢？显然有 \(r_n\ge l_1\)，那里的花费就是 \(0\)，所以我们只需要计算上面的式子就行了......时间复杂度 \(\mathcal O(n\log n)\).
叁、参考代码 ¶
没写第一种，写的第二种 因为它很短
#define Endl putchar('\n')
#define mp(a, b) make_pair(a, b)
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define fep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
const int maxn=1e5;
struct node{
int a, c;
node(){}
node(int A, int C): a(A), c(C){}
inline int operator <(const node rhs) const{
return a<rhs.a;
}
}p[maxn+5];
int n;
inline void input(){
n=readin(1);
int a, c;
rep(i, 1, n){
a=readin(1), c=readin(1);
p[i]=node(a, c);
}
sort(p+1, p+n+1);
}
signed main(){
input();
int maxx=p[1].a+p[1].c; ll ans=p[1].c;
rep(i, 2, n){
ans=ans+max(0, p[i].a-maxx);
maxx=max(maxx, p[i].a+p[i].c);
ans+=p[i].c;
}
printf("%lld\n", ans);
return 0;
}
肆、用到 の Trick
- \(\max\{c_i,a_j-a_i\}=c_i+\max\{0,a_j-a_i-c_i\}\)；
- 有时候，将一些相邻的边串联起来可以达到全部暴力连接的效果；
- 将问题转化为区间的问题；