CF-1014-D. Mishkin Energizer · znzryb

## 思路讲解

我写的算法相当于是一个贪心，就是先看可不可以插入出现次数最少的字符，然后看能不能插入次小的，再看能不能插入次次小的。

不断重复这个贪心操作，如果发现次数超过了 $2N$ 次还是无法达到平衡要求，那么直接输出 $-1$ ，反之如果中间哪次平衡了，那么就输出步骤数量以及保存好的步骤。

## AC代码

[https://codeforces.com/contest/2092/submission/315587701](https://codeforces.com/contest/2092/submission/315587701)



::: 源代码

```cpp
// Problem: D. Mishkin Energizer
// Contest: Codeforces - Codeforces Round 1014 (Div. 2)
// URL: https://codeforces.com/contest/2092/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e2)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
// char S[MAXN];
ll cnt[28];
char ingre[4]={'L','I','T'};

inline bool cmp(const char &a,const char &b){
	return cnt[a-'A']<cnt[b-'A'];
}

// LIT
inline void solve(){
	cin>>N;
	vector<char> s;
	for(int i=0;i<=26;++i){
		cnt[i]=0;
	}
	FOR(i,1,N){
		char a;
		cin>>a;
		s.pb(a);
		++cnt[a-'A'];
		// cin>>S[i];
	}
	// vector<ll> pos;
	bool canOper=false;
	for(int i=0;i<(int)s.size()-1;++i){
		if(s[i]!=s[i+1]){
			canOper=true;
		}
	}
	if(!canOper){
		cout<<-1<<"\n";
		return;
	}
	// 这道题目应该是O(n^2)的
	bool haveAns=false;
	vector<ll> ans;
	for(int i=1;i<=2*N+1;++i){
		if(cnt['L'-'A']==cnt['I'-'A'] && cnt['L'-'A']==cnt['T'-'A']){
			haveAns=true;
			break;
		}
		bool hasOp=false;
		sort(ingre,ingre+3,cmp);
		for(int i=0;i<3;++i){
			char obj=ingre[i];
			for(int i=0;i<(int)s.size()-1;++i){
				if(s[i]!=s[i+1]){
					if(s[i]!=obj && s[i+1]!=obj){
						s.insert(s.begin()+i+1,obj);
						ans.pb(i);
						++cnt[obj-'A'];
						hasOp=true;
					}
					if(hasOp){
						break;
					}
				}
				
			}
			if(hasOp){
				break;
			}
		}
		
	}
#ifdef LOCAL
    for(int i=0;i<s.size();++i){
    	cerr<<s[i];
    }
    cerr<<"\n";
    cerr<<"T:"<<cnt['T'-'A']<<"\n";
    cerr<<"I:"<<cnt['I'-'A']<<"\n";
    cerr<<"L:"<<cnt['L'-'A']<<"\n";
#endif
	if(haveAns){
		cout<<ans.size()<<'\n';
		for(int i=0;i<ans.size();++i){
			cout<<ans[i]+1<<"\n";
		}
	}else{
		cout<<-1<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2092/submission/315587701
*/
```


:::


## 心路历程（WA，TLE，MLE……）

哈哈，应该按照我最初想的写，不应该偷懒/