Commit8328776

committed

add gas station

1 parent3a2c9c1 commit8328776Copy full SHA for 8328776

File tree

+12

-2

lines changed

+12

-2

lines changed

Lines changed: 12 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,14 @@`
	`1`	`+##Guessing`
`1`	`2`
`2`		`-##TODO`
`3`		`-* write down thinking`
	`3`	+This problem is to find a UNIQUE station`i`, such that
`4`	`4`
	`5`	`+* SUM(gas[0 .. i-1]) - SUM(cost[0 .. i-1]) + SUM(gas[i .. end]) - SUM(cost[i .. end]) >= 0`
	`6`	`+* SUM(gas[0 .. i-1]) - SUM(cost[0 .. i-1]) < 0`
	`7`	`+`
	`8`	+`SUM(gas[0 .. i-1]) - SUM(cost[0 .. i-1]) < 0` is to guarantee that the`i` is unique.
	`9`	`+`
	`10`	+If`SUM(gas[0 .. i-1]) - SUM(cost[0 .. i-1]) < 0` and`SUM(gas[0 .. i-1]) - SUM(cost[0 .. i-1]) + SUM(gas[i .. end]) - SUM(cost[i .. end]) >= 0`, that is,`0 .. i-1` are all valid stations.
	`11`	`+`
	`12`	`+##Brute force`
	`13`	`+`
	`14`	+Just search through from`0` to`end`, find the valid`i`.

Comments

(0)