算法分析
下面参考 yxc大佬的题解 提出的感想
先求出:
-
从
1
走到i
的过程中,买入水晶球的最低价格dmin[i]
; -
从
i
走到n
的过程中,卖出水晶球的最高价格dmax[i]
;
然后枚举每个城市作为买卖的中间城市,求出 dmax[i] - dmin[i]
的最大值即可。
求 dmin[i]
和 dmax[i]
时,由于不是拓扑图,状态的更新可能存在环,因此不能使用动态规划,也不能使用Dijkstra算法,只能使用spfa
详细步骤
-
1、从
1
走到i
的过程中,从1
号点正向求到其他所有点的最低价格dmin[i]
-
2、从
n
走到i
的过程中,从n
号点反向求到其他所有点的最高价格dmax[i]
在这里我思考了很久,为什么不能正向从i
号点到n
号点求出最大价格?
原因是因为并不是所有点到终点都是可达的,必须保证,从1
号点走到i
号点时,i
号点一定能走到n
号点
如下图所示,1
号点能到达3
号点,然而3
号点却不能走到4
号点,若正向从i
号点到n
号点求出最大价格,以3
号点为分界点时,求得的最大差价格是dmax[3] - dmin[3] = 5
,然而3
号点却到达不了4
号点,图中答案是dmax[4] - dmin[4] = 2
,因此此做法不可行
因此,从1
号点能走到i
号点,从n
号点走到i
号点,则表示从1
号点到i
号点再到n
号点过程中不会发生间断
感谢羽兄提供的帮助~滑稽~
时间复杂度 $O(m)$
最坏 $O(nm)$
参考文献
算法提高课
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main{
static int N = 100010;
static int M = 2000010;
static int n;
static int m;
static int[] w = new int[N];
static int[] hs = new int[N];
static int[] ht = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int idx = 0;
static boolean[] st = new boolean[N];
static int[] cnt = new int[N];
static int INF = 0x3f3f3f3f;
static int[] dmin = new int[N];
static int[] dmax = new int[N];
static void add(int[] h,int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
//type == 0表示从1到k正向求最小值
//type == 1表示从n到k反向求最大值
static void spfa(int[] h,int[] dist,int type)
{
Queue<Integer> q = new LinkedList<Integer>();
if(type == 0)
{
Arrays.fill(dist, INF);
q.add(1);
dist[1] = w[1];
st[1] = true;
}
else
{
Arrays.fill(dist, -INF);
q.add(n);
dist[n] = w[n];
st[n] = true;
}
while(!q.isEmpty())
{
int t = q.poll();
st[t] = false;
for(int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
if((type == 0 && dist[j] > Math.min(dist[t], w[j])) || (type == 1 && dist[j] < Math.max(dist[t], w[j])))
{
if(type == 0) dist[j] = Math.min(dist[t], w[j]);
else dist[j] = Math.max(dist[t], w[j]);
if(!st[j])
{
q.add(j);
st[j] = true;
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
String[] s2 = br.readLine().split(" ");
for(int i = 1;i <= n;i ++) w[i] = Integer.parseInt(s2[i - 1]);
Arrays.fill(hs, -1);
Arrays.fill(ht, -1);
while(m -- > 0)
{
String[] s3 = br.readLine().split(" ");
int a = Integer.parseInt(s3[0]);
int b = Integer.parseInt(s3[1]);
int c = Integer.parseInt(s3[2]);
add(hs,a,b);
add(ht,b,a);//建立反向边
if(c == 2)
{
add(hs,b,a);
add(ht,a,b);
}
}
spfa(hs,dmin,0);
spfa(ht,dmax,1);
int res = -INF;
for(int i = 1;i <= n;i ++) res = Math.max(res, dmax[i] - dmin[i]);
System.out.println(res);
}
}
为什么不能正向从i号点到n号点求出最大价格?这个解释NB
请问能再解释一下
不能正向从i号点 到 n号点求出最大价格
的原因吗? 对于题解的图例, 3号点为分界点得到的最大价差是dmax[3]-dmin[3]=6-1=5 (在1号点买入 3号点卖出) , 这个可以理解; 然后4号点的例子是什么意思呢? 在4号点, 由于只能从1->2->4 4号点本来就只能在1号点买入 4号点卖出, 得到dmax[4]-dmin[4]=3-1=2啊? ?错啦,反向求只是为了预处理而已,正向求枚举i肯定tle啊,哪里是这样想的
不是把,你怎么求i~n的最短路?
枚举每个点肯定会超时啊
所以肯定是预处理啊。
如果n很小的话可以直接以i为起点啊
暴力spfa都行
但是这个n是1e6啊
感觉你这样想是有点面向答案了。
对的,因为n~i求最大值时起点是固定的,而i~n的话,起点i是不固定的,所以要建立反向边,反着跑一遍
好神奇,解释的太好了。
我也在想为什么要反向求max,学到了,感谢
不用hh
这里正反向建图,没有看懂啊, if(c == 2)
{
add(hs,b,a);
add(ht,a,b);
}
这里正向边和反向边正好反过来了,为啥不继续,正向的就a->b,反向的就b–>a
当
c==2
表示有双向边,把另外一边补上从i~n的最大值,我觉得还有另一个理解,就是如果是i~n的最大值,那么图走的顺序是就是正向的。这样的有一个结果就是k点(假设k的1~n)的最大值,可能不包括k~n了(因为可能会出现有向边的情况),但按照DP的思路,i,max[k]表示分割线之后所有值的最大值。因此只能“倒着走”,这样才可以从后面遍历过来,max[k]才可以表示k之后所有数的最大值。
tql