去年$Noip$的时候我并没有做过原题,然后考场上也没有想出正解,就写了个优化了一点的暴力:树状数组+差分,然后就$A$了$ovo$.
$Sol$
只要$O(N)$扫一遍,只要当前值比前一个值大,那么答案就累计这两个值的差的绝对值.$over.$
$Code$
#include<iostream> #include<cstdio> #define rg register #define ll long long using namespace std; int read() { int x=0,y=1;char c; c=getchar(); while(c<'0'||c>'9') {if(c=='-') y=-1;c=getchar();} while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*y; } int n; ll ans; int a[100010],b[100010]; int lowbit(int x) { return x&(-x); } void add(int x,int k) { for(rg int i=x;i<=n;i+=lowbit(i)) b[i]+=k; } ll sum(int x) { ll sum1=0; for(rg int i=x;i>=1;i-=lowbit(i)) sum1+=b[i]; return sum1; } int minn,l,r; int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); n=read();minn=210000000; for(rg int i=1;i<=n;i++) { a[i]=read(); minn=min(a[i],minn); add(i,a[i]-a[i-1]); } ans+=minn; add(1,-minn); if(a[1]!=0) l=0; for(rg int i=1;i<=n;i++) { int s=sum(i); if(s) { if(l==0) {l=i;r=i;minn=s;} else {minn=min(minn,s);r=i;} if(i!=n) continue ; } else if(l==0) continue; ans+=minn; add(l,-minn); if(r<n) add(r+1,minn); i=l-1;l=0; } printf("%lld",ans); return 0; }
#include<iostream> #include<cstdio> #define il inline #define Rg register #define go(i,a,b) for(Rg int i=a;i<=b;++i) #define ll long long using namespace std; il int read() { Rg int x=0,y=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*y; } int n,x,y;ll as; int main() { n=read(); go(i,1,n){y=read();if(y>x)as+=y-x;x=y;} printf("%lld ",as); return 0; }