[关闭]
@ysner 2018-07-26T22:00:06.000000Z 字数 1661 阅读 1923

简单题


题面

个加油站,第个加油站距离为,车遇站自动加油。现有油量可分配到各加油站中,来增大各站。有一任务,即在油量的前提下,从站到站,再将自带油量清,从站到站。问每个点在完成任务的前提下,最多能走到右边哪个站?

时限

解析

算法

首先显然有个贪心,就是从左向右走能不加油尽量不加油
正确性显然。与其把油量都堆在开头,不如使油量尽量靠后,这样才能更有助于从右往左,减少卡壳时所需油量。
然后我没看出来的是,从右往左可以直接在右端加上所有油
因为此时油加的位置没有其它附加影响了。

于是枚举每个点,枚举它能到的最右点,检验它是否能到。复杂度

算法

注意到答案不具有单调性
并不能说,上个点能达到最右点,这个点也一定能达到最右点。
因为受到出发点油量的影响。假如上个点油量特别大,而这个点特别小呢。

其实我们往右跑时可以同时兼顾向右时对可分配油量的需求,及向左时对可分配油量的需求

枚举左端点,然后一个劲地向右跑,该加油时就加油,直到可分配油量被耗完为止。这样保证能从左向右。

在此过程中,实时维护到当前点往返整个过程所需油量,如果往右跑的过程要加油。同时统计该段从右向左的油量需要(),不需要、可减,需要、可加。(表示从号站到号站的距离)

显然如果最大时油量还不为负,整个过程就一定合法,也就能走到该段右端点。而如果现在的与剩余油量之和大于等于就说明从右到左油量到不了负数,该答案合法。
复杂度
我觉得还是看代码清楚些

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define re register
  8. #define il inline
  9. #define ll long long
  10. #define max(a,b) ((a)>(b)?(a):(b))
  11. #define min(a,b) ((a)<(b)?(a):(b))
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=1e6+100;
  16. ll n,k,d[N],ans,w[N];
  17. il ll gi()
  18. {
  19. re ll x=0,t=1;
  20. re char ch=getchar();
  21. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. int main()
  27. {
  28. freopen("simple.in","r",stdin);
  29. freopen("simple.out","w",stdout);
  30. n=gi();k=gi();
  31. fp(i,2,n) d[i]=gi();
  32. fp(i,1,n) w[i]=gi();
  33. fp(i,1,n)
  34. {
  35. re ll had=0,now=w[i],res=k,mx=-1e18;ans=i;
  36. fp(j,i+1,n)
  37. {
  38. if(d[j]>now)
  39. if(d[j]-now<=res) res-=d[j]-now,had+=d[j]-now,now=0;
  40. else break;
  41. else now-=d[j];
  42. mx=max(mx,had);
  43. now+=w[j];had+=w[j]-d[j];
  44. if(had+res>=mx) ans=j;
  45. }
  46. printf("%lld ",ans);
  47. }
  48. puts("");
  49. fclose(stdin);
  50. fclose(stdout);
  51. return 0;
  52. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注