53 条题解
-
0
hahacool LV 10 @ 2008-09-16 21:24:26
用A表示从I-1到达I的油的变化量，
SUM数组表示A[1]+A[2]+。。+A，
用MINL表示SUM[1]到SUM的最小的SUM，
MINT表示SUM到SUM[M]的最小的SUM。
每次只要考虑MINT/MINL减去变化量大于0即可。
O（N）算法：
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：25ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 119ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：119ms
第100个！！！！
谢谢下面大牛！！！！！！！！
（这也是我得99题！！！！） -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 119ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：119ms
忘输出-1竟然都过了。。。。 -
0
smallapple LV 3 @ 2007-10-28 19:28:15
交了以后才想起来忘了输出-1了（平时正确率就是这么降的），结果竟然一次就直接通过了，真不容易
感觉俪元什么什么余同而言之不详，总结一下他们的思路写个明白的造福人民吧，也练习下表达能力。
设从第i-1到第i个景点汽油变化量为a[i] (i=2,…,n) 下标都是mod n意义下的
能从第p个城市出发的充要条件是对于任意的k都有a[p+1]+a[p+2]+…+a[k]>=0
令a[2]+…+a[i]=s[i]，s[1]=0 则等价为对任意的k,s[k]-s[p]>=0
所以所s[p]是所有的s中最小的，不过不知道要是油量变化之和不是0能不能做？？ -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms用sum[i]表示由第1个加油站开始开到第i+1个加油站途中把1~i加油站的油全加了然后油箱所剩的油为多少..sum[i]有可能
-
-1
hahacool
LV 10
@ 2008-09-16 21:24:26
