C. Line Empire

题目:C. Line Empire

考点：思维

题意：给一个长度为 $n$ 的数组 $X$ 以及 $a$ 和 $b$，并且 $0<X_1<X_2<\cdot \cdot \cdot <X_n$ ，求从 $0$ 出发，到占领 $X_n$ 的最小花费。存在如下两个操作：

• 将起点从 $C_1$ 转移到 $C_2$ ，花费 $a\ast |C_1-C_2|$
• 从起点 $C_1$ 出发占领 $C_2$，花费 $b\ast |C_1-C_2|$

需要注意的是，当要被占领的 $C_2$ 与起点 $C_1$ 之间存在未被占领的点时，$C_2$ 将不能被占领。转而言之，需要依次占领 $X_1、X_2、...、X_n$ 。

❌思路：通过题意能发现占领点的值一定会比出发点的值大，若要转移起点，则转移终点点一定会比起点大，即 $C_2>C_1$。面对一个新的待攻占点 $C_3$，我们有两种选择，①直接从起点 $C_1$ 出发攻占待攻占点 $C_3$，花费为 $b\ast |C_1-C_2|$，②先转移起点 $C_1$ 转移到 $C_2$，再从新的起点 $C_2$ 出发到新的待攻占点 $C_3$。两种情况取最小值。提取公式：$a\ast (C_2-C_1)+b\ast (C_3-C_2)$ ，用二分找出合适的点 $C_2$ ，此思路完全错误，过不了样例，可用此思路推一下第二个例子，便可知道错误之处。

✔思路：需要考虑的是从哪个点出发去攻占一个带攻占的点，转移起点会花费 $a\ast |C_2-C_1|$ ，需要判断这花费值不值，若后面还有 $m$ 个带攻占点，此时存在关系 $a\ast |C_2-C_1|\le |C_2-C_1|\ast m\ast b$ ，则表明将起点转移到 $C_2$ 是值得的，这样就能 $AC$ 了。

#include<stdio.h>

typedef long long ll;
const int N = 2e5 + 10;
ll s[N];
int n,a,b,k;

int main() {
	int t;
	scanf("%d",&t);
	while(t --) {
		
		scanf("%d %d %d",&n,&a,&b);
		for(int i=1;i<=n;i++) scanf("%lld",&s[i]);
		ll res = 0;
		int l = 0;
		for(int i=1;i<=n;i++) {
			res += b * (s[i] - s[l]);
			if((s[i] - s[l]) * a <= (s[i] - s[l]) * b * 1ll * (n - i)) {
				res += a * (s[i] - s[l]);
				l = i;
			}
		} 
		printf("%lld\n",res);
	}
	return 0;
}