ARC082D Sandglass
题意:有一个沙漏由A,B两个杯子组成。一共有X克沙子。
每秒会有一克沙子从上杯子流到下杯子,直到流完为止。
一共会有k次翻转杯子,第i次翻转杯子会在第 $r_i$ 秒。
有q组询问,每组形如 $t,a$ ,表示一开始A杯子在上,里面有a克沙子(B杯子里有 $X-a$ 克沙子),求第t秒的时候A杯子里有多少沙子。
$q,k\le 10^5$
题意:有一个沙漏由A,B两个杯子组成。一共有X克沙子。
每秒会有一克沙子从上杯子流到下杯子,直到流完为止。
一共会有k次翻转杯子,第i次翻转杯子会在第 $r_i$ 秒。
有q组询问,每组形如 $t,a$ ,表示一开始A杯子在上,里面有a克沙子(B杯子里有 $X-a$ 克沙子),求第t秒的时候A杯子里有多少沙子。
$q,k\le 10^5$
$A^\star$算法的经典应用----k短路问题。
$A^\star$算法:设$f(x)=g(x)+h(x)$,其中$g(x)$表示已花费代价,$h(x)$表示预估还需代价($h(x)$要$\le h^\star(x)$)表示每次找到f值最小的拿出来扩展。
给定一个n点m边的有向图,求从s到t的k短路。
首先求出所有点x到t的最短路$dis[x]$,接下来用$dis[x]$作为$h(x)$跑 $A^\star$ ,因为 $h(x)\le h^\star(x)$ ,所以第k次找到t就是k短路。