CodeChef-ROTMIN题意给定一个字符串sss允许对某一位进行加法(a→b,b→c,…,y→z,z→aa\to b,b\to c,\dots,y\to z,z\to aa→b,b→c,…,y→z,z→a) 最多qqq次 或减法(b→a,c→b,…,z→y,a→zb\to a,c\to b,\dots,z\to y,a\to zb→a,c→b,…,z→y,a→z) 最多ppp次求操作后字典序最小的字符串。题解容易观察到。为了使字典序最小可以将前缀尽可能的变为aaa对于加法操作只要不是z→az\to az→a字典序一定变大对于减法操作只要不是a→za\to za→z字典序一定变小所以就是贪心于是对于加法操作要么不做要么直接加到aaa对于减法操作就尽可能做直到成为aaa但假设你拿到fff你无法直接决策是f→e→⋯→af\to e\to\dots\to af→e→⋯→a还是f→g→⋯→z→af\to g\to\dots\to z\to af→g→⋯→z→a所以需要反悔操作具体地从前往后枚举你现在拿到了α\alphaα并有一个大根堆pqpqpq表示前面减法成为aaa操作中的使用次数令Aα−a\Alpha\alpha-aAα−a后面的那个是字符若减法操作足够你减为aaa即满足q≥Aq\ge\Alphaq≥A就直接减即q←q−Aq\gets q-\Alphaq←q−A并将A\AlphaA放入pqpqpq操作α←a\alpha\gets aα←a否则若前面某次操作可以从减法改成加法且比当前操作次数更大即pqpqpq堆顶元素β\betaβ满足β≥A\beta\ge \Alphaβ≥A且26−β≤p26-\beta\le p26−β≤p时就直接将β\betaβ改成加法加到aaaq←qβ−A,p←p−(26−β)q\gets q\beta-\Alpha,p\gets p-(26-\beta)q←qβ−A,p←p−(26−β)弹出β\betaβ放入A\AlphaA操作α←a\alpha\gets aα←a否则若加法操作足够你减为aaa即满足p≥26−Ap\ge26-\Alphap≥26−A就直接加即p←p−(26−A)p\gets p-(26-\Alpha)p←p−(26−A)操作α←a\alpha\gets aα←a否则使用减法尽可能小无需满足任何条件操作α←a(A−q),q←0\alpha\gets a(\Alpha-q),q\gets 0α←a(A−q),q←0具体讲一下第二步26−β≤p26-\beta\le p26−β≤p是保证β\betaβ可以通过加法成为aaa如果β\betaβ不还是aaa那么字典序就会不如操作前小β≥A\beta\ge \Alphaβ≥A是保证修改后的方法β\betaβ加法至aaa,α\alphaα减法至aaa更优之前的方法β\betaβ减法至aaa,α\alphaα加法至aaa证明Δp(26−A)(26−B)Δp′,ΔqBAΔq′\Delta_p(26-\Alpha)(26-\Beta)\Delta_p,\Delta_q\Beta\Alpha\Delta_qΔp​(26−A)(26−B)Δp′​,Δq​BAΔq′​然后就结束了。代码#includeiostream#includequeue#defineintlonglongusingnamespacestd;chars[120],*p,*q;#definegc()(((pq(p(qs)fread(s,1,120,stdin)),pq)?EOF:*q))inlineintread(){intres0,sign1;charcgc();for(;!isdigit(c);cgc())if(c-)sign-1;for(;isdigit(c);cgc())resres*10c-0;returnres*sign;}inlinestringreadstr(){string res;charcgc();for(;!(accz);cgc());for(;(accz);cgc())resc;returnres;}voidouts(string x){for(chari:x)putchar(i);}intt,n,P,Q,a[200005];string x,o;priority_queueintpq;voiddoes(){nread(),Pread(),Qread(),o;while(!pq.empty())pq.pop();x readstr();for(inti1;in;i){a[i]x[i]-a;if(Qa[i])Q-a[i],pq.push(a[i]),oa;else{if(!pq.empty()pq.top()a[i]P26-pq.top())Qpq.top()-a[i],P-26-pq.top(),pq.pop(),pq.push(a[i]),oa;else{if(P26-a[i])oa,P-26-a[i];elseochar(a[i]-Qa),Q0;}}}o\n;outs(o);}signedmain(void){ios::sync_with_stdio(0),cin.tie(0);tread();while(t--)does();return0;}