链接：https://www.nowcoder.com/acm/contest/117/I
来源：牛客网
第一行是一个正整数T(≤ 10)，表示测试数据的组数，
对于每组测试数据，
第一行是两个正整数n(≤ 1000000)和k(≤ 1000000000)，分别表示队列长度和最终的比赛总期待度，
接下来一行包含n个字符，表示这个队列，第i个字符表示队列里的第i个人，‘D‘表示大佬，‘M‘表示萌新，保证不会出现其它字符。
对于每组测试数据，输出一行，包含一个整数，表示最少的交换次数，无解输出-1。
2 3 1 DMM 3 3 DMM
1 -1
左右移动D，只会有3种结果+1 -1 0，所以先判断当前的数据最大的期望值是否符合输入，不符合则为-1，符合则计算当前的值-期望值的绝对值
#include<iostream> #include<algorithm> #define ll long long #include<cstdio> #include<cstring> #include<string> #include<cmath> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int N =1e6+5; char s[N]; int main() { int t; cin>>t; while(t--) { ll n,k; cin>>n>>k; cin>>s; ll cntm=0,cntd=0,ans=0; for(int i=0;i<n;i++) { if(s[i]==‘D‘) cntd++; else cntm++,ans+=cntd; } if(k<0||k>cntd*cntm) printf("-1\n"); else printf("%lld\n",abs(ans-k)); } return 0; }
原文：https://www.cnblogs.com/caiyishuai/p/9094022.html