题面
有\(n\)个加油站，第\(i\)和\(i+1\)个加油站距离为\(d_i\)，车遇\(i\)站自动加\(w_i\)油。现有\(k\)油量可分配到各加油站中，来增大各站\(w_i\)。有一任务，即在油量\(>0\)的前提下，从\(l\)站到\(r\)站，再将自带油量清\(0\)，从\(r\)站到\(l\)站。问每个点在完成任务的前提下，最多能走到右边哪个站？
- \(8pts\ n\leq1000\)
- \(31pts\ n\leq20000\)
- \(100pts\ n\leq10^6\)
时限\(5s\)
解析
\(8pts\)算法
首先显然有个贪心，就是从左向右走能不加油尽量不加油。
正确性显然。与其把油量都堆在开头，不如使油量尽量靠后，这样才能更有助于从右往左，减少卡壳时所需油量。 然后我没看出来的是，从右往左可以直接在右端加上所有油。 因为此时油加的位置没有其它附加影响了。于是枚举每个点，枚举它能到的最右点，检验它是否能到。复杂度\(O(n^3)\)。
\(39pts\)算法
注意到答案不具有单调性。
并不能说，上个点能达到最右点，这个点也一定能达到最右点。 因为受到出发点油量的影响。假如上个点油量特别大，而这个点特别小呢。其实我们往右跑时可以同时兼顾向右时对可分配油量的需求，及向左时对可分配油量的需求。
枚举左端点，然后一个劲地向右跑，该加油时就加油，直到可分配油量被耗完为止。这样保证能从左向右。
在此过程中，实时维护到当前点往返整个过程所需油量\(had\)，如果往右跑的过程要加油\(oil\)，\(had+=oil\)。同时统计该段从右向左的油量需要（\(w[j]-d[j]\))，不需要、\(had\)可减，需要、\(had\)可加。（\(d[j]\)表示从\(j-1\)号站到\(j\)号站的距离）
显然如果\(had\)最大时油量还不为负，整个过程就一定合法，也就能走到该段右端点。而如果现在的\(had\)与剩余油量之和大于等于\(max\)，就说明从右到左油量到不了负数，该答案合法。
复杂度\(O(n^2)\)#include#include #include #include #include #include #define re register#define il inline#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;const int N=1e6+100;ll n,k,d[N],ans,w[N];il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}int main(){ freopen("simple.in","r",stdin); freopen("simple.out","w",stdout); n=gi();k=gi(); fp(i,2,n) d[i]=gi(); fp(i,1,n) w[i]=gi(); fp(i,1,n) { re ll had=0,now=w[i],res=k,mx=-1e18;ans=i; fp(j,i+1,n) { if(d[j]>now) if(d[j]-now<=res) res-=d[j]-now,had+=d[j]-now,now=0; else break; else now-=d[j]; mx=max(mx,had); now+=w[j];had+=w[j]-d[j]; if(had+res>=mx) ans=j; } printf("%lld ",ans); } puts(""); fclose(stdin); fclose(stdout); return 0;}