Chinaunix首页 | 论坛 | 博客
  • 博客访问: 878881
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-12-30 14:44:03

有一个环路,中间有N个加油站,加油站里面的油是g1,g2...gn,加油站之间的距离是d1,d2...dn,问其中是否能找到一个加油站,使汽车从这个加油站出发,走完全程。
 
 
 
计算辅助数组f(i),其含义为从i点开始到达i+1时,汽车所剩的油。有:
             f(i) = g(i)-d(i)
若f(i)<0 则显然从i点出发不可能完成任务。
 
 
题目的O(n)解法依赖于以下结论,在面试的时间内,要迅速发现这个规律不是一件容易的事。
从任意一个点s开始扫描,如果到点e之前汽车没油了,那么说明从s到e-1中的所有点出发,都不可能完成任务。
 
设从s点到e时,油箱中剩下的油为t(s,e). 完成不了任务,说明t(s,e)<0
证明:
显然t(s,e) = f(s) + t(s+1,e)
若从s开始是合理的,则必有f(s)>=0
因此t(s+1,e) = t(s+1,e)-f(s)
若t(s,e)<0,那么必有t(s+1,e)<0,显然从s+1开始也完成不了任务。
由此可得结论。
 
对于任意一个O(n)复杂度的DP题目,都需要类似的结论做支持,即f(n)仅与一个变量n有关,如果和两个变量相关即f(s,n)那么复杂度必定不为O(n)。
这个题目中直观看到相关的变量有起始点和终止点2个,所以要通过分析,剔除和无关的变量,消除无需计算的部分,才能得出正确结果。
 
代码(codepad.org已验证)

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX 1000
  4. int test(int input[], int size){
  5.     if(input == NULL ) return -1;
  6.     int i = 0;
  7.     int result[MAX] = {0};
  8.     result[0] = input[0];
  9.         printf("result[%d] = %d\n", i,result[i]);
  10.     int count = 0;
  11.         i++;
  12.     while(count<size && i<=size*2){
  13.         if(result[i-1]>=0){
  14.             count++;
  15.             result[i] = result[i-1] + input[i%size];
  16.         }
  17.         else{
  18.             result[i] = input[i%size];
  19.             count = 0;
  20.         }
  21.                 printf("result[%d] = %d\n", i,result[i]);
  22.         i++;
  23.     }
  24.     if(count == size)
  25.         return (i-1)%size;
  26.     return -1;
  27. }
  28. int *prepare(int dis[], int gas[],int size){
  29.     if(dis == NULL || gas==NULL) return NULL;
  30.     int * ret = (int*)malloc(sizeof(int)*size);
  31.     int i = 0;
  32.     for(;i<size;i++){
  33.         ret[i] = gas[i] - dis[i];
  34.     }
  35.         return ret;
  36. }

  37. int main(){
  38.     int dis[] = {2,3,2};
  39.     int gas[] = {1,1,5};
  40.     int *input = prepare(dis,gas,3);
  41.     int ret = test(input, 3);
  42.     printf("%d \n",ret);
  43. }

阅读(2510) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

kebey20042017-03-16 08:33:24

4*7 done?