Description n层楼，每层有一个指示牌指示当前是上一层还是下一层，每经过一层指示牌就会反向，对于一个起点i，最后要经过多少步才能到第0层或者第n+1层，对于每个i输出结果 Input 第一行一整数n表示楼层数，之后一个长度为n的字符串表示初始状态每层的指示方向(1<=n<=1e6) Output 输出n个整数，第i个整数表示初始时在第i层时要经过多少步才能出去，如果永远出不去则输出-1 Sample Input 3 UUD Sample Output 5 6 3
input
10 UUDUDUUDDUoutput
5 12 23 34 36 27 18 11 6 1这个题我写的比较蠢，记录每个左边几个U右边几个D，再记录U和D的id前缀和，方向要分清楚，该位的U/D要分清楚情况
看有说队列的https://blog.csdn.net/v5zsq/article/details/71171709
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; long long n; char ch[1000005]; int lrs[1000005][2]; long long dsum[1000005]; long long usum[1000005]; int main() { while(~scanf("%lld",&n)) { scanf("%s",ch); memset(lrs,0,sizeof(lrs)); int cu=0; for(int i=0;i<n;i++) { if(ch[i]=='U') { cu++; } lrs[i+1][0]=cu; } int cd=0; for(int i=n-1;i>=0;i--) { if(ch[i]=='D') { cd++; } lrs[i+1][1]=cd; } /* for(int i=1;i<=n;i++) { cout<<lrs[i][0]<<" : "<<lrs[i][1]<<endl; } */ int cntd=1; dsum[0]=0; for(int i=n;i>=1;i--) { if(ch[i-1]=='D') { dsum[cntd]=dsum[cntd-1]+i; cntd++; } } int cntu=1; usum[0]=0; for(int i=1;i<=n;i++) { if(ch[i-1]=='U') { usum[cntu]=usum[cntu-1]+(n+1-i); cntu++; } } /* for(int i=1;i<cntd;i++) { cout<<"D: "<<dsum[i]<<endl; } for(int i=1;i<cntu;i++) { cout<<"U: "<<usum[i]<<endl; } */ for(int i=1;i<=n;i++) { long long ans=0; long long dnum,unum; if(lrs[i][0]>lrs[i][1]) { ans+=(n+1-i); if(ch[i-1]=='U') { dnum=lrs[i][1]; unum=lrs[i][1]; } else { unum=lrs[i][1]; dnum=lrs[i][1]-1; } } else if(lrs[i][1]>lrs[i][0]) { ans+=(i); if(ch[i-1]=='U') { dnum=lrs[i][0]; unum=lrs[i][0]-1; } else { dnum=lrs[i][0]; unum=lrs[i][0]; } } else { if(ch[i-1]=='D') { ans+=(n+1-i); unum=lrs[i][0]; dnum=lrs[i][0]-1; } else { ans+=(i); dnum=lrs[i][0]; unum=lrs[i][0]-1; } } //cout<<"dnum:"<<dnum<<endl; //cout<<"unum:"<<unum<<endl; int td=lrs[i][1]; if(ch[i-1]=='D') td--; int dd=td-dnum; ans+=2*(dsum[td]-dsum[dd]-dnum*i); int tu=lrs[i][0]; if(ch[i-1]=='U') tu--; int uu=tu-unum; ans+=2*(usum[tu]-usum[uu]-unum*(n+1-i)); printf("%lld ",ans); }printf("\n"); } }
