很容易想到其实也不容易 一段连续的数字如果后面的数字比前面一个小那么后面这个数字就不用 t e l e p o r t teleport teleport ,但是后面的数字比前面的大那么就要 a n s ans ans 加上他们的差值。
对于被 0 0 0 隔开的连续区间一定需要 t e l e p o r t teleport teleport 。
奇妙的来了
思路的第一点操作的序列是减 1 1 1 后的序列(就是走一遍走到末后再来 t e l e p o r t teleport teleport )。
第二点我一开始用了双指针去找连续区间,然后连续区间的数量减 1 1 1 就是 0 0 0 隔开所必需的 t e l e p o r t teleport teleport 。
按照这样下去其实就能 A C AC AC 了,但是我把初始序列不减 1 1 1 因为我要找隔开的区间嘛,有初始为 1 1 1 的减了不就视作隔开但其实没有吗。最后我发现答案错了我找完隔开区间忘记把序列减 1 1 1 了 ,但是我发现 a n s − c n t ans-cnt ans−cnt 答案减去隔开区间刚好就是正确答案。太有意思了,开始应该加上隔开区间所必需的 t e l e p o r t − > a n s + c n t − 1 teleport-> ans+cnt-1 teleport−>ans+cnt−1 ,最后竟然要 a n s − c n t ans-cnt ans−cnt ,所以隔开区间不用找了,直接 a n s ans ans 初始化为 − 1 -1 −1 不就好了,真有意思。 Think Twice, Code Once
#include<bits/stdc++.h>#defineilinline#definegetgetchar#defineputputchar#defineisisdigit#definereregister#defineintlonglong#definedfor(i,a,b)for(re int i=a;i<=b;++i)#definedforr(i,a,b)for(re int i=a;i>=b;--i)#definedforn(i,a,b)for(re int i=a;i<=b;++i,put(10))#definemem(a,b)memset(a,b,sizeof a)#definememc(a,b)memcpy(a,b,sizeof a)#definepr114514191981#definegg(a) cout<<a,put(32)#defineINF0x7fffffff#definett(x) cout<<x<<'\n'#definelsi<<1#definersi<<1|1#definela(r) tr[r].ch[0]#definera(r) tr[r].ch[1]#definelowbit(x)(x&-x)usingnamespace std;typedefunsignedint ull;intread(void){
re int x=0,f=1;re char c=get();while(!is(c))(f=c==45?-1:1),c=get();while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();return x*f;}voidwrite(int x){
if(x<0) x=-x,put(45);if(x>9)write(x/10);put((x%10)^48);}#definewriteln(a)write(a),put(10)#definewritesp(a)write(a),put(32)#definewritessp(a)put(32),write(a)constint N=2e5+10,M=3e4+10,SN=1e4+10,mod=998244353;int n,a[N];signedmain(){
int T=read();while(T--){
n=read();
re int ans=-1,cnt=0;dfor(i,1,n) a[i]=read();
re int l=0,r=0;// while(r<=n&&l<=n)// {
// while(!a[l]&&l<=n) ++l;// ++cnt,r=l;// while(a[r]&&r<=n) ++r;// l=r;// }// cout<<cnt<<"DF"<<endl;// ans+=cnt-1;dfor(i,1,n)if(a[i]<=a[i-1])continue;else ans+=a[i]-a[i-1];writeln(ans);}return0;}